全排列问题

题意

输入 n，按字典序输出 1..n 的所有排列。每个数字占 5 个字符宽度。

思路

题目要求的是完整全排列，并且 n <= 9。Python 标准库 itertools.permutations 会按照输入序列的顺序生成所有排列。

所以只需要：

构造序列 1..n；
枚举所有排列；
按题目要求格式化输出。

Python 知识

permutations(range(1, n + 1)) 生成 1..n 的所有排列。
f"{number:5d}" 表示整数右对齐，占 5 个字符宽度。
"".join(...) 把一行中的多个格式化字段拼成字符串。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md

代码

python

1
2
3
4
5
6from itertools import permutations

n = int(input())

for order in permutations(range(1, n + 1)):
    print("".join(f"{number:5d}" for number in order))

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

int n;
int choose[15];
bool vis[15];

void dfs(int dep) {
    if (dep == n) {
        for (int i = 0; i < n; i++)
            cout << setw(5) << choose[i];
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = true;
            choose[dep] = i;
            dfs(dep + 1);
            vis[i] = false;
        }
    }
}

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

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-14 14:54
 * update_at: 2026-08-14 14:54
 */
/* P1706 全排列问题：used 数组记录已用数字，回溯时恢复。 */

#include <iostream>
#include <iomanip>

const int max_n = 10;  // n 最大为 9

int n;
int chosen[max_n];  // chosen[pos]：第 pos 位填的数字
int used[max_n];    // used[value] = 1 表示数字 value 已被前面的位置使用

// 填第 pos 位（0 起始），所有位置填完就输出一个排列。
void dfs(int pos) {
    if (pos == n) {
        for (int i = 0; i < n; i += 1) {
            std::cout << std::setw(5) << chosen[i];
        }
        std::cout << '\n';
        return;
    }

    // 每一位可以尝试任意一个还没用过的数字。
    for (int value = 1; value <= n; value += 1) {
        if (used[value]) {
            continue;  // 这个数字已经出现在前面的位置
        }
        used[value] = 1;    // 前进阶段：标记 value 被占用
        chosen[pos] = value;  // 记录当前位的选择
        dfs(pos + 1);
        used[value] = 0;    // 回溯阶段：释放 value，让下一个分支可以再用
    }
}

int main() {
    std::cin >> n;
    dfs(0);
    return 0;
}

复杂度

一共有 $n!$ 个排列，每行输出 n 个数，时间复杂度为 $O(n\cdot n!)$ ，空间复杂度为 $O(n)$ 。

总结

全排列输出题很适合用 itertools.permutations 学习 Python 枚举工具。它直接表达“枚举所有顺序”。

目录

题意

思路

Python 知识

代码

Guide 风格代码

复杂度

总结