生成1~n的排列，以及生成可重集的排列

#include <iostream>
using namespace std;

void printPermutation(int n, int* A, int cur)
{
	if (cur == n) { // 递归边界
		for (int i = 0; i < n; i++) {
			printf("%d ", A[i]);
		}
		printf("
");
	}
	else {
		for (int i = 1; i <= n; i++) { // 尝试在A[cur]中填各种整数i
			int ok = 1;
			for (int j = 0; j < cur; j++) {
				if (A[j] == i) {
					ok = 0; // 如果i已经在A[0]~A[cur-1]出现过，则不能再选
				}
			}
			if (ok) {
				A[cur] = i;
				printPermutation(n, A, cur + 1); // 递归调用
			}
		}
	}
}

int main()
{
	int A[20];
	printPermutation(5, A, 0); // 生成1~5的排列
	return 0;
}

循环变量 i 是当前考察的A[cur]。为了检查元素i是否已经用过，上面的程序用到了一个标志变量ok，初始值为1（真），如果发现有某个A[j] == i 时，则改为0（假）。如果最终ok仍未1，则说明i没有在序列中出现过，把它添加到序列末尾（A[cur] = i）后递归调用。

声明一个足够大的数组A，然后调用printPermutation(n, A, 0)，即可按字典序输出1~n的所有排列。

如果问题变成输入数组p，并按字典序输出数组A个元素的所有全排列，则需要修改代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int P[100], A[100];

// 输出数组p中元素的全排列。数组p中可能有重复元素
void printPermutation(int n, int* P, int* A, int cur) {
	if (cur == n) {
		for (int i = 0; i < n; i++) printf("%d ", A[i]);
		printf("
");
	}
	else for (int i = 0; i < n; i++) {
		if (!i || P[i] != P[i - 1]) {
			int c1 = 0, c2 = 0;
			for (int j = 0; j < cur; j++) {
				if (A[j] == P[i]) {
					c1++;
				}
			}
			for (int j = 0; j < n; j++) {
				if (P[i] == P[j]) {
					c2++;
				}
			}
			if (c1 < c2) {
				A[cur] = P[i];
				printPermutation(n, P, A, cur + 1);
			}
		}
	}
}

int main()
{
	int i, n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &P[i]);
	}
	sort(P, P + n);
	printPermutation(n, P, A, 0);
	return 0;
}

最后用STL中的库函数next_permultation

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
	int n, p[10];
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &p[i]);
	}
	sort(p, p + n); // 排序，得到p的最小排列
	do {
		for (int i = 0; i < n; i++) {
			printf("%d ", p[i]); // 输出排列p
		}
		printf("
");
	} while (next_permutation(p, p + n)); // 求下一个排列

	return 0;
}

上述代码同样适用于可重集。