YeungYeah 的乱写地

枚举排列

 Posts  

如何按字典序从小到大输出前 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. 将当前首元素记录。
  3. 每次将记录的元素右移 1 位（交换位置），生成一个排列
  4. 直到元素移到最右边，回到步骤 2
  5. 当出现了初始序列时，排列生成完毕

具体代码可以参照 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;
}

相关文章：