---
title: "03-排列"
created: 2025-12-02
tags:
  - 项目
aliases:
  - 排列
---
# 排列

## 题目 [排列](https://www.acwing.com/problem/content/825/)

![[image-43314ef3.png]]

## 思路分析

java中没有next\_permutation 得老老实实写dfs 最后附上next\_permutation实现

## 代码实现

```java
import java.util.Scanner;

import java.io.*;

public class Main {

    // 存储当前排列路径的数组

    private static int[] path;

    // 标记数组，用于标记某个元素是否已在当前排列中使用

    private static boolean[] st;

    // 输入的整数 n，表示要排列的数字的范围是 [1, n]

    private static int n;

    // 使用 BufferedWriter 来高效地输出结果

    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();

        path = new int[n];

        st = new boolean[n];

        dfs(0);

        bw.flush();// 刷新缓冲区，将所有内容输出

    }

    private static void dfs(int u) throws Exception {

        if (u == n) {

            for (int i = 0; i < n; i++)

                bw.write(path[i] + " ");

            bw.write("\n");

        } else {

            for (int i = 0; i < n; i++)

                if (!st[i]) {

                    st[i] = true;

                    path[u] = i + 1;

                    dfs(u + 1);

                    st[i] = false;

                }

        }

    }

}
```

不使用静态变量也能让dfs函数访问到局部变量的方法：

```java
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        boolean[] vis = new boolean[n];
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 局部内部类可以访问外部类的所有成员变量和方法
        class Inner {
            public void dfs(int u) throws IOException {
                if (u == n) {
                    for (int i = 0; i < n; i++) {
                        bw.write((nums[i] + 1) + " ");
                    }
                    bw.write("\n");
                } else {
                    for (int i = 0; i < n; i++) {
                        if (vis[i] == false) {
                            vis[i] = true;
                            nums[u] = i;
                            dfs(u + 1);
                            vis[i] = false;
                        }
                    }
                }
            }
        }
        Inner inner = new Inner();
        inner.dfs(0);
        bw.flush();
    }
}
```

next\_permutation实现

- **从右往左找到第一个递增的位置** `i`（即找到第一个满足 `a[i] < a[i + 1]` 的 `i`）。
- **从右往左找到第一个比** `a[i]` **大的数字** `j`。
- **交换** `a[i]` **和** `a[j]`。
- **反转** `i + 1` **之后的子数组**。

基本实现   tle：

```java
import java.util.Arrays;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] a = new int[n];

        // 初始化数组 a 为 [1, 2, 3, ..., n]

        for (int i = 0; i < n; i++) {

            a[i] = i + 1;

        }

        // 打印初始排列

        do {

            for (int num : a) {

                System.out.print(num + " ");

            }

            System.out.println();

        } while (nextPermutation(a)); // 生成下一个排列，直到没有更大的排列

    }

    // 实现类似 C++ 中 next_permutation 的方法

    private static boolean nextPermutation(int[] a) {

        int i = a.length - 2;

        // 从右往左找到第一个递增的位置 i

        while (i >= 0 && a[i] >= a[i + 1]) {

            i--;

        }

        // 如果 i < 0，说明当前排列是最大的，返回 false 表示没有下一个排列了

        if (i < 0) return false;

        int j = a.length - 1;

        // 从右往左找到第一个比 a[i] 大的元素 j

        while (a[j] <= a[i]) {

            j--;

        }

        // 交换 a[i] 和 a[j]

        swap(a, i, j);

        // 反转 i + 1 之后的元素

        reverse(a, i + 1, a.length - 1);

        return true;

    }

    // 辅助方法：交换数组中的两个元素

    private static void swap(int[] a, int i, int j) {

        int temp = a[i];

        a[i] = a[j];

        a[j] = temp;

    }

    // 辅助方法：反转数组中从 start 到 end 的部分

    private static void reverse(int[] a, int start, int end) {

        while (start < end) {

            swap(a, start, end);

            start++;

            end--;

        }

    }

}
```

结合`BufferedWriter` 优化 I/O   ac

```java
import java.io.BufferedWriter;

import java.io.OutputStreamWriter;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws Exception {

        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;

        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        do {

            for (int num : a) {

                bw.write(num + " ");

            }

            bw.write("\n");

        } while (nextPermutation(a));

        bw.flush();

        bw.close();

    }

    private 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--;

        }

        swap(a, i, j);

        reverse(a, i + 1, a.length - 1);

        return true;

    }

    private static void swap(int[] a, int i, int j) {

        int temp = a[i];

        a[i] = a[j];

        a[j] = temp;

    }

    private static void reverse(int[] a, int start, int end) {

        while (start < end) {

            swap(a, start, end);

            start++;

            end--;

        }

    }

}
```

## 同类题型

## 视频讲解

---

**项目分区导航**： [[02-打印矩阵|打印矩阵]] ⬅️ | 03-排列 |  ➡️ [[04-数组排序|数组排序]]