#include <iostream> #include <algorithm> using namespace std; template <typename T> /* 把升序的排列（当然，也可以实现为降序）作为当前排列开始，然后依次计算当前排列的下一个字典序排列。 对当前排列从后向前扫描，找到一对为升序的相邻元素，记为i和j（i < j）。 如果不存在这样一对为升序的相邻元素，则所有排列均已找到，算法结束； 否则，重新对当前排列从后向前扫描，找到第一个大于i的元素k，交换i和k ，然后对从j开始到结束的子序列反转， 则此时得到的新排列就为下一个字典序排列。 这种方式实现得到的所有排列是按字典序有序的， 这也是C++ STL算法next_permutation的思想。 算法实现如下 */ //字典序 void CalcAllPermutation(T perm[], int num)//num为排列中元素的个数 { if (num < 1) return; while (true) { int i; for (i = num - 2; i >= 0; --i) { if (perm[i] < perm[i + 1])//从右向左，找到第一对上升的序列 break; } if (i < 0) break; // 已经找到所有排列 int k; for (k = num - 1; k > i; --k)//从右向左找到第一个比perm[i]大的数 { if (perm[k] > perm[i]) break; } swap(perm[i], perm[k]); //交换 reverse(perm + i + 1, perm + num);//逆反一下 } } //递归 void CalcAllPermutation_R(int perm[], int s, int e) { if( s >= e ) { //输出 return; } for(int i=s;i<=e;i++) { swap(perm[i],perm[s]); CalcAllPermutation_R(perm, s+1,e) ; swap(perm[i],perm[s]); } } int main() { const int NUM = 12; char perm[NUM]; for (int i = 0; i < NUM; ++i) perm[i] = 'a' + i; CalcAllPermutation(perm, NUM); }
字符串的组合：
题目：输入一个字符串，输出该字符串中字符的所有组合。举个例子，如果输入abc，它的组合有a、b、c、ab、ac、bc、abc。 本题也可以用递归的思路来求字符串的组合。 假设我们想在长度为n的字符串中求m个字符的组合。我们先从头扫描字符串的第一个字符。针对第一个字符，我们有两种选择：一是把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选取m-1个字符；二是不把这个字符放到组合中去，接下来我们需要在剩下的n-1个字符中选择m个字符。这两种选择都很容易用递归实现。下面是这种思路的参考代码： void Combination(char* string) { if(string == NULL) return; int length = strlen(string); vector<char> result; for(int i = 1; i <= length; ++ i) { Combination(string, i, result); } } void Combination(char* string, int number, vector<char>& result) { if(number == 0) { vector<char>::iterator iter = result.begin(); for(; iter < result.end(); ++ iter) printf("%c", *iter); printf("\n"); return; } if(*string == '\0') return; result.push_back(*string); Combination(string + 1, number - 1, result); result.pop_back(); Combination(string + 1, number, result); } 由于组合可以是1个字符的组合，2个字符的字符……一直到n个字符的组合，因此在函数void Combination(char* string)，我们需要一个for循环。另外，我们一个vector来存放选择放进组合里的字符 方法二： 用一个数组，模拟2进制加法器，某一位为1，则取对应的字符，若为0则不取，就能够实现字符组合。