手链样式
小明有3颗红珊瑚,4颗白珊瑚,5颗黄玛瑙。
他想用它们串成一圈作为手链,送给女朋友。
现在小明想知道:如果考虑手链可以随意转动或翻转,一共可以有多少不同的组合样式呢?
请你提交该整数。不要填写任何多余的内容或说明性的文字。
圆(环)排列:围成一个圆,圆旋转一下就是同一个排列。因此从n个中取r个的圆排列数为
项链排列:项链是立体的,存在翻转的情况,项链排列数为
但是翻转对于左右对称的情况是没有影响的,不需要除以2。
所以项链排列的公式为:
(引用自:https://www.cnblogs.com/lemonbiscuit/p/7776008.html)
方法二:全排列,去掉相同的
在v中存翻转前后的两种结果,对任意新的一种组合方式,在v中进行匹配查找。
do...while结构
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */vector<string> v;//存储已出现的情况 int main(int argc, char** argv)
{string str = "aaabbbbccccc";int count = 0;v.clear();do{vector<string>::iterator it;for(it = v.begin(); it != v.end(); it++){//从*it的0位置开始找,返回第一次成功匹配str的首字符在*it中的位置if((*it).find(str,0) != string::npos) break;//如果在已有的里面能找到,即是重复的,判断下一个 }if(it != v.end()) continue;string str2 = str+str;//可以任意转动 v.push_back(str2); reverse(str2.begin(), str2.end()); //需要algorithm头文件 可以翻转 v.push_back(str2); count++;}while(next_permutation(str.begin(),str.end())) ;cout<<count<<endl;return 0;
}
// 1170
while...结构
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */vector<string> v;//存储已出现的情况 int main(int argc, char** argv)
{string str = "aaabbbbccccc";int count = 1;v.clear();string str2 = str+str;v.push_back(str2);reverse(str2.begin(),str2.end());v.push_back(str2); while(next_permutation(str.begin(),str.end())) {vector<string>::iterator it;for(it = v.begin(); it != v.end(); it++){//从*it的0位置开始找,返回第一次成功匹配str的首字符在*it中的位置if((*it).find(str,0) != string::npos) break;//如果在已有的里面能找到,即是重复的,判断下一个 }if(it != v.end()) continue;string str2 = str+str;//可以任意转动 v.push_back(str2); reverse(str2.begin(), str2.end()); //需要algorithm头文件 可以翻转 v.push_back(str2); count++;};cout<<count<<endl;return 0;
}
// 1170
方法三:
在v外的字符串str2中存储旋转和翻转的结果,在str2中匹配查找v中组合
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */vector<string> v;//存储已出现的情况 int main(int argc, char** argv)
{string str = "aaabbbbccccc";int count = 1;int flag = 0;v.push_back(str);while(next_permutation(str.begin(),str.end())){flag = 0;//转动string str2 = str + str;vector<string>::iterator it;for(it = v.begin(); it != v.end(); it++){if(str2.find(*it) != string::npos){flag = 1;//找到了该种组合方式,不再查找 break;}}//翻转if(flag == 0){//转动后,在v中仍没有找到相同组合 reverse(str2.begin(),str2.end());for(it = v.begin(); it != v.end(); it++){if(str2.find(*it) != string::npos){flag = 1;break;}}}//继转动后,翻转后,在v中仍没有找到相同组合,确定为一种新组合,添加进v if(flag == 0){v.push_back(str);count++;} }cout<<count<<endl;return 0;
}
// 1170
方法四、map<string,bool> mp 代替 vector 和 flag
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */map<string,bool> mp;//存储已出现的情况
int colorNum[3] = {2,4,5};//假定从红色开始放置,所以红色已经少了一个
char color[4] = "rwy";//红色,白色,黄色bool pd(string str)
{int len = str.size();str += str;//旋转 for(int i = 0; i < len; i++){//取str中的第i个(包括第i个)开始的len个字符 string temp = str.substr(i,len);if(mp[temp] == 1)return 0;//如果在mp中存在,则不增加计数,返回0 }return 1;
}int dfs(string str)
{if(!colorNum[0] && !colorNum[1] && !colorNum[2]){//所有颜色的数量都为0了,得出了一个新的排列 if(pd(str) == 0) return 0;//该排列所属组合已经计数了,返回0,跳出本层dfs reverse(str.begin(),str.end());//翻转 if(pd(str) == 0)return 0;//该排列的翻转排列所属组合已经计数了,返回0,跳出本层dfs //该排列的旋转和翻转所属组合均未计数,添加进mp,计数加一,返回1 ,跳出本层dfsmp[str] = true; return 1;}int count = 0;for(int i = 0; i < 3; i++){if(!colorNum[i]) continue;//该颜色数量为0,结束本层循环,直接进行i+1层循环 string temp = str;colorNum[i]--; temp += color[i];count += dfs(temp);colorNum[i]++;}return count;
}
int main(int argc, char** argv)
{mp.clear();cout<<dfs("r")<<endl;return 0;
}
// 1170