P1706 全排列问题

May 8, 2026 · 5 分钟阅读 · 枚举 ·

文章目录

题目信息

字段	内容
题号	P1706
难度	普及-
知识点	`next_permutation`、全排列、枚举

题目描述

输出整数 1 到 N（N ≤ 9）的所有字典序全排列，每行 N 个数，每个数宽度为 5 个字符（右对齐）。

解题思路

核心思想：`next_permutation` 生成全排列

利用 C++ STL 中的 next_permutation，不断将当前排列变换为字典序中的下一个排列，直到不存在更大的排列为止。

初始化细节：将数组初始化为 n, n-1, ..., 1（降序），这样第一次调用 next_permutation 时，它会重排为升序 1, 2, ..., n 并返回 true，即恰好从最小的排列开始枚举。

初始数组:  n, n-1, ..., 1
第 1 次 next_permutation → 1, 2, ..., n    （最小排列）
第 2 次 next_permutation → 1, 2, ..., n-1, n
...
第 n! 次 next_permutation → n, n-1, ..., 1  （最大排列）
第 n!+1 次 → 返回 false，停止

共需调用 n! 次 next_permutation，恰好等于全排列的总数。

完整代码

C++

#include <bits/stdc++.h>
using namespace std;

int a[10], j = 1, n;

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

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        a[i] = n - i + 1;   // 初始化为 n, n-1, ..., 1
        j *= i;              // 计算 n!
    }

    for (int i = 1; i <= j; ++i) {
        next_permutation(a + 1, a + n + 1);
        for (int k = 1; k <= n; ++k)
            cout << setw(5) << a[k];
        cout << '\n';
    }

    return 0;
}

注：setw(5) 设置每个数字的输出宽度为 5（默认右对齐），等价于题目要求的"每个数宽度为 5 个字符"。next_permutation 来自 <algorithm>，bits/stdc++.h 包含了所有常用头文件。

关键代码讲解

1. 初始化为降序

for (int i = 1; i <= n; ++i) {
    a[i] = n - i + 1;   // a[1]=n, a[2]=n-1, ..., a[n]=1
}

a 初始为 n, n-1, ..., 1。第一次 next_permutation 会把它变成 1, 2, ..., n，即从最小的排列开始输出。

2. 计算排列总数

j *= i;   // i=1..n 时，j 累计为 1×2×...×n = n!

j 最终等于 n!，即全排列的总数，也就是需要调用 next_permutation 的次数。

3. `next_permutation` 的工作方式

next_permutation(a + 1, a + n + 1);

将 [a[1], a[n]] 区间内的序列变换为字典序下一个排列（原地修改）。当已是最大排列时返回 false。

4. 固定宽度输出

cout << setw(5) << a[k];

setw(5) 设置下一个输出项的宽度为 5，不足部分左侧补空格，实现右对齐效果。

复杂度分析

方法	时间复杂度	空间复杂度
`next_permutation` 全排列	`O(N × N!)`，共 `N!` 个排列，每个排列输出 `N` 个数	`O(N)`（数组 `a`）

N! 增长极快，当 N = 9 时 9! = 362880，输出量约 180 万字符。

易错点

初始化顺序：必须从 n, n-1, ..., 1 开始（而非 1, 2, ..., n），否则第一次 next_permutation 输出的是第二小的排列，会漏掉最小的 1 2 ... n。
next_permutation 返回值：true 表示有下一个排列，false 表示已到最大排列。循环次数为 n!，而非依赖返回值控制。
setw 不持效：setw 只影响下一次输出，需每次都写；可用 cout << setfill(' ') 配合初始化填充字符。

其他语言解法

Python

import itertools
import sys

def solve() -> None:
    n = int(sys.stdin.readline())
    for perm in itertools.permutations(range(1, n + 1)):
        sys.stdout.write(''.join(f'{x:>5}' for x in perm) + '\n')


if __name__ == '__main__':
    solve()

JavaScript

'use strict';

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin', 'utf8').trim();
const n = parseInt(input, 10);

const a = [];
for (let i = 1; i <= n; ++i) a.push(i);

// 手写 next_permutation
function nextPermutation(arr) {
    let i = arr.length - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i < 0) return false;

    let j = arr.length - 1;
    while (arr[j] <= arr[i]) j--;
    [arr[i], arr[j]] = [arr[j], arr[i]];

    let l = i + 1, r = arr.length - 1;
    while (l < r) {
        [arr[l], arr[r]] = [arr[r], arr[l]];
        l++;
        r--;
    }
    return true;
}

const out = [];
do {
    out.push(a.map(x => String(x).padStart(5)).join(''));
} while (nextPermutation(a));

process.stdout.write(out.join('\n'));

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

func nextPermutation(a []int) bool {
    i := len(a) - 2
    for i >= 0 && a[i] >= a[i+1] {
        i--
    }
    if i < 0 {
        return false
    }
    j := len(a) - 1
    for a[j] <= a[i] {
        j--
    }
    a[i], a[j] = a[j], a[i]
    l, r := i+1, len(a)-1
    for l < r {
        a[l], a[r] = a[r], a[l]
        l++
        r--
    }
    return true
}

func main() {
    in := bufio.NewReader(os.Stdin)
    var n int
    fmt.Fscan(in, &n)

    a := make([]int, n)
    for i := 0; i < n; i++ {
        a[i] = i + 1
    }

    out := bufio.NewWriter(os.Stdout)
    for {
        for _, v := range a {
            fmt.Fprintf(out, "%5d", v)
        }
        fmt.Fprintln(out)
        if !nextPermutation(a) {
            break
        }
    }
    out.Flush()
}

Java

import java.io.*;

public class Main {

    static boolean nextPermutation(int[] a) {
        int i = a.length - 2;
        while (i >= 0 && a[i] >= a[i + 1]) i--;
        if (i < 0) return false;

        int j = a.length - 1;
        while (a[j] <= a[i]) j--;
        int tmp = a[i]; a[i] = a[j]; a[j] = tmp;

        int l = i + 1, r = a.length - 1;
        while (l < r) {
            tmp = a[l]; a[l] = a[r]; a[r] = tmp;
            l++; r--;
        }
        return true;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = fs.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = i + 1;

        // 手动构造固定宽度字符串（避免 String.format 的内存开销），流式输出
        do {
            for (int v : a) {
                if (v < 10)       bw.write("    " + v);
                else if (v < 100) bw.write("   " + v);
                else              bw.write("  " + v);
            }
            bw.newLine();
        } while (nextPermutation(a));

        bw.flush();
    }

    // FastScanner（避免 Scanner MLE）
    static class FastScanner {
        private final BufferedInputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) {
            in = new BufferedInputStream(is);
        }

        private int readByte() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c, sign = 1, val = 0;
            do { c = readByte(); } while (c <= ' ' && c != -1);
            if (c == '-') { sign = -1; c = readByte(); }
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = readByte();
            }
            return val * sign;
        }
    }
}