标签：arr 排列洛谷 int DFS 后缀 static P1706

全排列问题

题目描述

P1706 全排列问题 - 洛谷

按照字典序输出自然数 \(1\) 到 \(n\) 所有不重复的排列，即 \(n\) 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 \(n\)。

输出格式

由 \(1 \sim n\) 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 \(5\) 个场宽。

样例 #1

样例输入 #1

样例输出 #1

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

提示

\(1 \leq n \leq 9\)。

解析

前言

不要使用printf格式化输出，性能十分的低！！！

DFS回溯法求全排列

\(DFS\) 最显著的特征在于其 递归调用自身。同时与 \(BFS\) 类似，\(DFS\) 会对其访问过的点打上访问标记，在遍历时跳过已打过标记的点，以确保 每个点仅访问一次。

回溯法是一种经常被用在\(DFS\) (深度优先搜索) 和\(BFS\)(广度优先搜索)的技巧。

其本质是：走不通就回头。

伪码

int ans = 最坏情况;

void dfs(传入数值) {
  if (到达目的地){
     ans = 从当前解与已有解中选最优;
  	 return...
  }
  for (遍历所有可能性)
    if (可行) {
      进行操作;
      dfs(缩小规模);
      撤回操作;
    }
}

实现

import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    //book[i]代表i已经被选择过了
    static boolean[] book;
    //存储当前的排列
    static int[] num;
    static int N;

    static void dfs(int n) {
        //已经搜索到最后一个数了
        if (n > N) {
            for (int i = 1; i <= N; ++i) {
                System.out.print("    " + num[i]);
            }
            System.out.println();
        }
        //遍历所有数
        for (int i = 1; i <= N; ++i) {
            //如果i已经被选择，则跳过
            if (book[i]) continue;
            //给i这个数打上标记，代表选上i
            book[i] = true;
            //将i存入当前排列答案中
            num[n] = i;
            //继续搜索下一个数
            dfs(n + 1);
            //撤回标记
            book[i] = false;
        }
    }

    public static void main(String[] args) {
        N = sc.nextInt();
        num = new int[N + 1];
        book = new boolean[N + 1];
        dfs(1);
    }

下一个排列

下一个排列的定义是：

给定数字序列的字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

简单来说就是，下一个数比当前数大且尽可能的小

推导

举个例子，求2543的下一个排列

对于非严格递减的数没有下一个排列，所以2543的后缀543没有下一个排列对此我们能做的就是修改2的值

又因为需要新的排列数比当前数大且尽可能的小

所以，选择后缀543中最小的数与2交换，变成3542

而3542并不是尽可能小的，因为它交换后，其后缀542仍是降序的

将其后缀542排序后，才是正确答案3245

但如果要求456 2543的下一个排列呢

它的下一个排列是456 3245，观察发现前面的456并没有改变

因为需要比当前数大且尽可能的小，而它的后缀2543已经可以做到这一点了，拓展至任意情况这个特性依然满足

过程描述

下一个排列的描述：

从后向前查找第一个相邻的升序的元素对（代表这个后缀有下一个排列），即找到最后一个arr[i]<arr[i+1]。（此时[i+1,end)是非严格递减的）
在后缀[i+1,end)中找到最小的大于arr[i]的数，记为arr[k]。由于后缀[i+1,end)是非严格递减的，所以从后向前找到第一个大于arr[i]的数即可
交换arr[i]和arr[k]
对后缀[i+1,end)排序，最小化。由于交换后仍为非严格递减的，逆置[i+1,end)即可使其升序
若在步骤1中无符合条件的相邻的元素对，则说明此时数组是非严格降序的，没有下一个排列了

实现

import java.util.Scanner;

public class Main {
    public static void swap(int[] arr, int x, int y) {
        arr[x] ^= arr[y] ^ (arr[y] = arr[x]);
    }

    //作用：生成下一个排列 (数组范围[l,r])
    public static boolean nextPermutation(int[] arr, int l, int r) {
        if (arr.length <= 1) return false;
        int i = r - 1;
        while (i >= l && !(arr[i] < arr[i + 1])) --i;
        if (i == l - 1) return false;
        int k = r;
        while (arr[i] >= arr[k]) --k;
        swap(arr, i, k);
        for (int left = i + 1, right = r; left < right; ++left, --right) swap(arr, left, right);
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; ++i) arr[i] = i;
        do {
            for (int i = 1; i <= n; ++i) System.out.print("    " + arr[i]);
            System.out.println();
        } while (nextPermutation(arr, 1, n));
    }
}

对比

	DFS回溯	下一个排列
时间复杂度	\(O(n\times n!)\)	\(O(n\times n!)\)
空间复杂度	在不考虑栈消耗下，需要标记数组 \(O(n)\)	数组内原地操作 \(O(1)\)
是否支持序列包含重复元素	不支持（除非进行特判）	完全支持
适用程度	DFS回溯算法适用程度更广，应当优先掌握	仅适用于排列问题

参考资料

标签：arr,排列,洛谷,int,DFS,后缀,static,P1706
From： https://www.cnblogs.com/Cattle-Horse/p/16904164.html

洛谷P1706 全排列问题