递归实现排列型枚举

题目描述

把 $1 \sim n$ 这 $n$ 个整数排成一行，输出所有可能的次序（ $1 \le n \le 9$ ）。输入：一个整数 $n$ 。输出：按字典序从小到大输出所有方案，每行一个，同行相邻两数用空格隔开。例如 $n=3$ 时输出：

text

思路

把排列看成从左到右逐个位置填数字：dfs(pos) 从 1 到 n 依次尝试每个未使用的数字填进第 pos 个位置，标记后递归、返回后取消标记（回溯），pos 到达 n 时输出当前排列。由于每层从小到大枚举，输出天然满足字典序。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-10-01 09:32
# update_at: 2026-10-01 09:32

import sys
from collections.abc import Iterator


def generate_permutations(n: int) -> Iterator[str]:
    """生成 1 到 n 的所有全排列，每项格式化为行末带空格的字符串。"""
    chosen = [False] * (n + 1)
    path = [0] * n

    def dfs(pos: int) -> Iterator[str]:
        if pos == n:
            yield " ".join(map(str, path)) + " "
            return
        for num in range(1, n + 1):
            if not chosen[num]:
                chosen[num] = True
                path[pos] = num
                yield from dfs(pos + 1)
                chosen[num] = False

    yield from dfs(0)


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    token = next(data, None)
    if token is None:
        return
    n = int(token)
    lines = list(generate_permutations(n))
    sys.stdout.write("\n".join(lines) + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-06 11:13
 * update_at: 2026-10-06 11:13
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 9 + 5;

ll n;                  // 题目给出的 n，排列长度
ll path[MAXN];         // path[pos] 表示第 pos 个位置填的数字
bool used[MAXN];       // used[i] 表示数字 i 是否已经被选用

// dfs(pos)：这一层在为第 pos 个位置选择一个未使用的数字
void dfs(ll pos) {
    if (pos == n) { // 前 n 个位置全部填满，输出当前排列
        for (ll i = 0; i < n; i++) printf("%lld ", path[i]);
        printf("\n");
        return;
    }
    // 从小到大尝试每个数字，保证输出按字典序
    for (ll i = 1; i <= n; i++) {
        if (used[i]) continue;
        used[i] = true;
        path[pos] = i;
        dfs(pos + 1);
        used[i] = false; // 回溯恢复现场
    }
}

int main() {
    scanf("%lld", &n);
    dfs(0);
    return 0;
}

递归实现排列型枚举

目录

题目描述

思路

参考代码