如何按字典序从小到大输出前 n 个数的所有排列？
递归调用
将数字分成两部分：
每次移除一个待定元素添加到前缀序列末尾，进行下一次递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void print_permutation(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;
print_permutation(n, A, cur+1); //递归调用
}
}
}
|
直接生成
该方法直接获取到排列序列
- 将元素排序，记录初始序列。
- 将当前首元素记录。
- 每次将记录的元素右移 1 位（交换位置），生成一个排列
- 直到元素移到最右边，回到步骤 2
- 当出现了初始序列时，排列生成完毕
具体代码可以参照 std 标准库里面的方法next_permutation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include<cstdio>
#include<algorithm> //包含 next_permutation
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;
}
|