全排列

题目描述

给定一个由互不相同的小写字母、已按 a<b<…<z 升序排好的字符串 $S$ （ $1\le|S|\le 6$ ），按字典序输出 $S$ 的全部 $|S|!$ 个排列，每行一个。字典序：两等长串从左到右找第一个不同位置，字母小的在前。样例：abc → 六行 abc acb bac bca cab cba。

思路

输入已升序，对 s 反复调用 next_permutation(s, s+n)、每次输出当前串，直到回到起点即可。n ≤ 6 时最多 720 行。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22#!/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-09-29 23:06
# update_at: 2026-09-29 23:06

import sys
from itertools import permutations


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    s = next(data).decode()  # 题面唯一的输入：按字母序排好的小写字母串

    # 输入串已按字母序排好：permutations 逐位按下标从小到大取字符，
    # 同一层先试小下标（小字母），故生成顺序天然就是字典序，无需排序。
    print(*map(''.join, permutations(s)), sep='\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-05 05:18
 * update_at: 2026-10-05 05:18
 */
// main.cpp：roj/1199 全排列，n<=6。
// 输入已按字母升序排好，用 STL 的 next_permutation 按字典序枚举全部排列。

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

typedef long long ll;

char s[7];          // 输入串，长度 1..6，s[n] 留给 '\0'
int n;              // 实际长度

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 读入一行小写字母串
    string t;
    if (!(cin >> t)) return 0;
    n = (int)t.size();
    for (int i = 0; i < n; i++) s[i] = t[i];
    s[n] = '\0';

    // 输入已升序，先输出一次当前排列，再反复调用 next_permutation
    cout << s << '\n';
    while (next_permutation(s, s + n)) {
        cout << s << '\n';
    }

    return 0;
}

目录

题目描述

思路

参考代码