【编程题】字符串排列组合

/************************* 字符组合问题 输入一个字符串，长度为n,选出m个字符组合 *******************************/ /************************** 思想：    1.递归算法    2.依次遍历字符串        对于当前字符str[ii],我们有两种选择    一种是 选择该字符(即是将字符加入结果集)  则下一步要做的是  在剩下 的 n-1个字符中选择m-1字符 - 递归调用    另一种是  不选择该字符(即是不将该字符加入结果集) 则下一步要做的是  在剩下的 n-1个字符中选择 m个字符-递归调用    3.当选择的字符个数达到 m个，则输出。 **************************/ void  combinationOfChar(char *str,int len,int n,int m,vector<char> result) { if (str == NULL) return; if (m == 0) { for (int ii = 0; ii < result.size(); ++ii) cout << result[ii]; cout << endl; } if (n==len) return; //将当前字符放入结果集 result.push_back(str[n]); combinationOfChar(str,len, n + 1, m - 1, result); //将上一次选择取消，进行另一种选择，不选择该字符 result.pop_back(); combinationOfChar(str, len,n + 1, m, result); } /****************************** 字符串排列 ******************************/ /***************************** 思想：    1.递归算法    2.依次遍历字符串    3.拿当前字符分别与后面字符(包括自己)交换    4.递归调用 next+1  将下一个字符依次与他下面的字符交换    5.直至达到字符串末尾，输出字符串    6.交换完成，应再次交换回来    7.注意处理相同字符的情况       当字符 str[cur]与其后字符str[ii]交换时，判断[cur,ii]之间是否有重复字符，如果有重复字符，则不交换，否则则交换 ***************************/ bool isSwap(char *str,int start,int end) { while (start<end) { if (str[start] == str[end]) { return false; } else { start++; } } return true; } void permution(char* str, int len,int next) { if (str[next] == '\0') { cout << *str; } //版本一  有可能会产生重复 for (int ii = next; ii < len; ++ii) { swap(&str[next],&str[ii]); permution(str, len, next + 1); swap(&str[next], &str[ii]); } //版本二   消除重复 for (int ii = next; ii < len; ++ii) { if (isSwap(str, next, ii)) { swap(&str[next], &str[ii]); permution(str, len, next + 1); swap(&str[next], &str[ii]); } } }