#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("\n"); } 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("\n"); } 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("\n"); } while (next_permutation(p, p + n)); // 求下一个排列 return 0; }
上述代码同样适用于可重集。