全排列生成

概念讲解

什么是全排列？

全排列是指将 n 个元素按照所有可能的顺序排列。

示例： [1, 2, 3] 的全排列：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

全排列个数

n 个元素的全排列有 n! 个。

生成方法

1. STL next_permutation

123456789101112#include <algorithm>
using namespace std;

int a[] = {1, 2, 3};
int n = 3;

do {
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
} while (next_permutation(a, a + n));

注意： 使用前要先排序。

2. 回溯法

123456789101112131415161718192021int path[10];
bool used[10];

void permutation(int depth, int n) {
    if (depth == n) {
        for (int i = 0; i < n; i++) {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }
    
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            path[depth] = i;
            used[i] = true;
            permutation(depth + 1, n);
            used[i] = false;  // 回溯
        }
    }
}

组合枚举

从 n 个数中选 k 个

12345678910111213141516int path[10];

void combination(int depth, int start, int n, int k) {
    if (depth == k) {
        for (int i = 0; i < k; i++) {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }
    
    for (int i = start; i <= n; i++) {
        path[depth] = i;
        combination(depth + 1, i + 1, n, k);
    }
}

子集枚举

二进制枚举

12345678910void subset(int n) {
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                cout << i + 1 << " ";
            }
        }
        cout << endl;
    }
}

考点分析

初赛考查方式

1. 选择题： 全排列个数
2. 程序阅读： 理解全排列生成过程
3. 编程题： 全排列应用

常见题型

• 全排列生成
• 组合枚举
• 子集枚举

例题精讲

例题 1：全排列

题目： 生成 1~n 的全排列。

解答：

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

int main() {
    int n;
    cin >> n;
    
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
    }
    
    do {
        for (int i = 0; i < n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    } while (next_permutation(a, a + n));
    
    return 0;
}

例题 2：组合

题目： 从 n 个数中选 k 个数的所有组合。

解答：

12345678910111213141516171819202122232425262728#include <iostream>
using namespace std;

int path[10];

void combination(int depth, int start, int n, int k) {
    if (depth == k) {
        for (int i = 0; i < k; i++) {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }
    
    for (int i = start; i <= n; i++) {
        path[depth] = i;
        combination(depth + 1, i + 1, n, k);
    }
}

int main() {
    int n, k;
    cin >> n >> k;
    
    combination(0, 1, n, k);
    
    return 0;
}

练习题

1. 洛谷 P1706 全排列问题

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

int main() {
    int n;
    cin >> n;
    
    int a[n];
    for (int i = 0; i < n; i++) {
        a[i] = i + 1;
    }
    
    do {
        for (int i = 0; i < n; i++) {
            printf("%5d", a[i]);
        }
        cout << endl;
    } while (next_permutation(a, a + n));
    
    return 0;
}

2. 洛谷 P1157 组合的输出

123456789101112131415161718192021222324252627#include <iostream>
#include <iomanip>
using namespace std;

int path[25];
int n, r;

void combination(int depth, int start) {
    if (depth == r) {
        for (int i = 0; i < r; i++) {
            cout << setw(3) << path[i];
        }
        cout << endl;
        return;
    }
    
    for (int i = start; i <= n; i++) {
        path[depth] = i;
        combination(depth + 1, i + 1);
    }
}

int main() {
    cin >> n >> r;
    combination(0, 1);
    return 0;
}

3. 洛谷 P2404 自然数的拆分问题

1234567891011121314151617181920212223242526#include <iostream>
using namespace std;

int path[15];
int n;

void dfs(int depth, int start, int remaining) {
    if (remaining == 0) {
        for (int i = 0; i < depth - 1; i++) {
            cout << path[i] << "+";
        }
        cout << path[depth - 1] << endl;
        return;
    }
    
    for (int i = start; i <= remaining; i++) {
        path[depth] = i;
        dfs(depth + 1, i, remaining - i);
    }
}

int main() {
    cin >> n;
    dfs(0, 1, n);
    return 0;
}

易错点

⚠️ 注意：

1. next_permutation 使用前要先排序
2. 回溯时要恢复现场
3. 组合枚举要注意去重
4. 子集枚举可以用二进制