题目链接

全排列

题目描述

给定一个整数 ，请按字典序输出数字 的所有排列。

输入：

  • 一行一个整数

输出：

  • 按字典序输出所有排列。每行输出 个整数，数字之间用单个空格分隔

解题思路

按字典序生成全排列有两种常见方法：

  • 使用内置/标准库的“下一个排列”算法（next_permutation）。从初始数组 开始，循环输出并不断生成下一个排列，直到没有下一个排列。
  • 使用回溯（DFS）：按从小到大的顺序依次选择未使用的数字，天然得到字典序。实现略长，但思路直观。

这里代码采用第一种方法实现（Python 使用 itertools.permutations，传入有序序列即可按字典序产生）。

代码

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

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

    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    iota(a.begin(), a.end(), 1);

    do {
        for (int i = 0; i < n; ++i) {
            if (i) cout << ' ';
            cout << a[i];
        }
        cout << '\n';
    } while (next_permutation(a.begin(), a.end()));

    return 0;
}

import java.util.*;

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 t = a[i]; a[i] = a[j]; a[j] = t;
        int l = i + 1, r = a.length - 1;
        while (l < r) { int x = a[l]; a[l] = a[r]; a[r] = x; l++; r--; }
        return true;
    }

    static void print(int[] a) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            if (i > 0) sb.append(' ');
            sb.append(a[i]);
        }
        System.out.println(sb.toString());
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = i + 1;
        print(a);
        while (nextPermutation(a)) print(a);
    }
}

from itertools import permutations

n = int(input().strip())
for p in permutations(range(1, n + 1)):
    print(' '.join(map(str, p)))

算法及复杂度

  • 算法：next_permutation / permutations 按字典序枚举
  • 时间复杂度：（共 个排列，每个输出需 ）
  • 空间复杂度：（除输出外的额外空间）