排列数、组合数生成算法

输入n，r
输出C（r，n），A（r，n）即所有的排列方式，组合方式

先考虑组合，如果能够得到所有的组合数情况，只要分别对这些组合做排列计算即可
要想输出所有的组合情况，必须按照一定的次序，可以按照字典顺序输出所有情况。假设n=4，r=2，那么第一个组合数是1 2，第二个是13。。。第六个是3 4。可以看出组合数的倒数第一位不超过n，倒数第二位不超过n-1，。。。倒数第r位不能超过n-r+1，同时右边的数总是大于左边的数。所以对于任意给定的一个组合，如果其最右边没达到所能达到的最大值，只需将最右边数+1即可得到下一个组合数，如果最右边已经不能再大了，考虑倒数第二位，如果倒数第二位没有达到最大值，将倒数第二位+1，同时这位以后的数字依次比前一个数大1，如果倒数第二位不能再大了，考虑倒数第三位，将倒数第三位+1，同时这位以后的数字依次比前一个数大1。。。。直到倒数第r个数即第一个数已经不能再大了
算法实现如下：

int next_combination(int *num, int n, int r)
{
bool has_next = false;
int i = 0;
for (i = 0; i < r; i++)
if (num[r - i - 1] < n - i) {
num[r - i - 1]++;
has_next = true;
break;
}
if (has_next) {
for (int j = i; j > 0; j--) {
num[r - j] = num[r - j - 1] + 1;
}
return 1;
}
return 0;
}

下面考虑排列
这里也按照字典顺序输出所有排列，假设有排列S₁，S₂，，。。。S_n，要想得到下一个排列，则需要从右向左扫描，找出第一个位置S_m，满足S_m<S_m+1，S_m左边的部分不变，调整S_m及其右边部分即可得到下一个排列。S_m右边部分是递减的，从右向左扫描，找出第一个S_k，满足S_k>S_m，交换S_k，S_m   的值，现在的情况是，从S_m+1到S_n是递减的，再将这部分元素逆置，得到最终结果，算法描述如下：

int next_permutation(int *num, int n)
{
if (n <= 1)
return 0;
int m = n - 2;
while (num[m] > num[m + 1] && m >= 0)
m--;
if (m < 0)
return 0;
int k = n - 1;
while (num[m] > num[k])
k--;
std::swap(num[m], num[k]);
int p = m + 1;
int q = n - 1;
while (p < q) {
std::swap(num[p], num[q]);
p++;
q--;
}
return 1;
}

回到开头，输入n，r，先调用next_combination得到一个排列，再对这个排列调用next_permutation即可得到最后的排列情况。如果只需要组合情况，只需调用next_combination

测试程序：

for (int i = 0; i < r; i++)

res[i] = i + 1;

int *tmp = new int[r];

do {

memcpy(tmp, res, r * sizeof(int));

do {

output_combination(tmp, r);

     } while (next_permutation(tmp, r));

} while (next_combination(res, n, r));

delete tmp;

delete res;