例：输出从1,2......m,中任取k个数的所有组合。m=5，k=3时有543,542,541,532,531,521,432,431,421,321有C(m,k)个。
法一：枚举方法
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 int main() 5 { 6 int n; 7 cin >> n; 8 for (int x = 1; x <= n - 2; ++x) 9 for (int y = x + 1; y <= n - 1; ++y) 10 for (int z = y + 1; z <= n; ++z) 11 printf("%d %d %d\n", x, y, z); 12 system("pause"); 13 return 0; 14 }
n = 5时将输出123,124,125,134,135,145,234，235,245,345。
法二：递归实现
设函数comb（int m，int k)是找出1,2，.....m中任取k个数的所有组合，当组合的第一个数字选定后，其后的数字的就是从余下的m-1个数选k-1个数的组合，问题转化为求comb（m-1, k-1).需要一个全局数组存放结果，将确定的k个数字组合的第一个数存储在a[k]中，求出一个组合后输出a数组中的一个组合。每个组合的第一个数字可以是m,m-1,.....k.函数确定组合的第一个数字后，如果还为确定组合的其余元素，则继续递归，否则输出。
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 const int MAX = 10; 5 int a[10]; 6 void comb(int m, int k) 7 { 8 int i, j; 9 for (i = m; i >= k; --i) 10 { 11 a[k] = i; //每个组合的第一个数可以是m,m-1.....k 12 if (k > 1) 13 comb(i - 1, k - 1); //k>1继续递归 14 else 15 { 16 for (j = a[0]; j > 0; --j) 17 printf("%d", a[j]); 18 printf("\n"); 19 } 20 } 21 } 22 int main() 23 { 24 int m, k; 25 cin >> m >> k; 26 a[0] = k; //a[0]用来表示k 27 comb(m, k); 28 return 0; 29 }
输入m=5，k=3，输出543,542,541,532,531,521,432,431,421,321。
全排列的生成:
最简单的方法就是使用STL<algorithm>中的next_permutation,其返回bool值，不过经常用就啥都忘了。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> //for sort and next_permutation 4 using namespace std; 5 int main() 6 { 7 int n; 8 scanf("%d", &n); 9 int p[n]; 10 for (int i = 0; i < n; ++i) 11 scanf("%d", &p[i]); 12 sort(p, p + n); //处理乱序输入，适用于可重复集合 13 do { 14 for (int i = 0; i < n; ++i) 15 printf("%d ", p[i]); 16 printf("\n"); 17 } while (next_permutation(p, p + n)); //bool next_purmutation(begin, end) 18 system("pause"); 19 return 0; 20 }
递归生成1-n的全排列(无重复元素）：如abc的全排列有abc,acb,bac,bca,cba,cab,一共3！个。
设对R={r1,r2,......rn}全排列，设Ri = R - {ri},perm(X)表示集合X的全排序，（ri）perm（X)表示X全排序前加前缀ri
全排列的递归定义：设n是集合中元素个数
r n = 1
perm(R)= (r1)perm(R1)
......
(rn)perm(Rn)
如果给定集合{a,b,c,d},所有可能的排列由下列排列组成
1.以a开头的后面跟着（b,c,d)的所有排列
2.以b开头的后面跟着(a,c,d)的所有排列
3.以c开头的后面跟着（a,b,d)的所有排列
4.以d开头的后面跟着（a,b,c)的所有排列
递归线索是“后面跟着。。。的所有排列”，若能够解决n-1个元素集合的排列，就可以解决n个元素集合的排列问题。
处理时将所有数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> //for swap(x,y) 4 using namespace std; 5 void perm(char *a, int i, int n) 6 { 7 if (i == n) //递归出口 8 { 9 for (int j = 0; j <= n; ++j) 10 printf("%c", a[j]); 11 printf("\n"); 12 } 13 else 14 { 15 for (int j = i; j <= n; ++j) 16 { 17 swap(a[i], a[j]); 18 perm(a, i + 1, n); 19 swap(a[i], a[j]); //第二个swap用于恢复与第一个数交换 20 } 21 } 22 } 23 int main() 24 { 25 char a[3] = {'a', 'b', 'c'}; 26 perm(a, 0, 2); //初始调用perm(list, 0, n-1) 27 system("pause"); 28 return 0; 29 }
执行后输出abc,acb,bac,bca,cba,cab，按照字典序输出。
根据这种思路还有一种方法确定递归函数：（参考刘汝佳《算法竞赛入门经典》）
1已经确定的前缀序列，以便输出
2需要进行全排列的元素集合，以便依次选作第一个元素
伪代码：
void perm(序列A， 集合S）
{
if（S为空）
输出序列A；
else 按照从小到大的顺序依次考虑S的每个元素v
perm（在A的末尾添加v后得到的新序列，S-{v}）；
}
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 void perm(int n, int *a, int cur) 5 { 6 int i, j; 7 if (cur == n) //递归边界 8 { 9 for (i = 0; i < n; ++i) 10 printf("%d", a[i]); //处理字母时只需要改成printf("%c", a[i]+'a'-1); 11 printf("\n"); 12 } 13 else for (i = 1; i <= n; ++i) //在a[cur]中填各种整数i 14 { 15 bool ok = 1; 16 for (j = 0; j < cur; ++j) 17 if (a[j] == i) 18 ok = 0; //若i在a[0]...a[cur-1]出现过，则不能再选 19 if (ok) //ok为真说明i没有在序列中出现过 20 { //就把i添加到序列末尾后递归调用，这样处理就不必保存集合S了 21 a[cur] = i; 22 perm(n, a, cur + 1); 23 } 24 } 25 } 26 int main() 27 { 28 int a[] = {1, 2, 3}; 29 perm(3, a, 0); //初始调用perm(n, a, 0) 30 system("pause"); 31 return 0; 32 }
输出结果123,132,213,231,312,321，改成字母后输出abc,acb,bac,bca,cba,cab。