这篇文章主要讲用Java如何清晰的解决全排列的问题。最后会有一道洛谷的全排列衍生的题目来加强练习。全排列算法是一个经典的算法题目，在c++中algorithm的算法头文件也有提供全排列算法的函数。可见它的通用程度很高。还有一个月也快要蓝桥杯比赛了。在蓝桥杯比赛里有很多这种递归、回溯、dfs的问题。

解决递归问题——先暴力，再优化

  1. 在脑子里或者纸笔模拟走几遍  --（会模拟出类似树的东西）
  2. 找出边界条件  --（大概意思是递到叶子节点开始归）
  3. 拆分子问题 重复问题 每次递归都要处理的问题  --（每个节点都要做的事情）

其中最难就是写出递归的过程，写的出递归一般就写的出一定程度的优化。

递归可以暴力解决这个问题，但是递归是指数级时间复杂度、一般还要再次优化才能过题。

// 虽然是这么个套路，但我还是做过类似的才会 ^_^

优化方法有

  • 备忘录、记忆化搜索     （记录已经得到过的值，减少重复计算）
  • 剪枝                              （加点判断条件，提前结束递归）
  • 通过递归得出dp方程    （感觉要积累很多经验才看得出来）
  • ...（不知道了..）

全排列问题

全排列比较直观的回溯实现 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Permutations {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
			nums[i] = i+1; 
		}
        
        
        
        //创建一个二维列表，赋全排列的值
        List<List<Integer>> permutations = new ArrayList<>();
        //表示当前排列
        List<Integer> current = new ArrayList<>();
        
        //用于标记某数字是否使用过
        boolean[] used = new boolean[nums.length];
        backtrack(nums, current, used, permutations);
        
        //输出打印结果
        for (List<Integer> permutation : permutations) {
            for (int num : permutation) {
                System.out.print(num+"  ");
            }
            System.out.println();
        }
        
    }

    
    //回溯算法
    private static void backtrack(int[] nums, List<Integer> current, boolean[] used,
                                  List<List<Integer>> permutations) {
        //当前排列排满后 添加到总排列表中并该次递归
    	if (current.size() == nums.length) {
            permutations.add(new ArrayList<>(current));
            return;
        }

    	
        for (int i = 0; i < nums.length; i++) {
        	//当数字未被使用
            if (!used[i]) {
                used[i] = true;	//标记为已使用
                current.add(nums[i]); //添加数字
                
                //继续搜索数字并添加。最后会添加
                backtrack(nums, current, used, permutations);  
                

                //回溯
                current.remove(current.size() - 1);  //移除这个数字
                used[i] = false;  // 标记为未使用
            }
        } 
    }
}

输入输出说明：

输出一个n，表示1~n的全排列

输出所有全排列情况，用空格间隔。

例如：

通过一个二维列表来存储每个全排列的情况，用一个数组used代表是否使用过这个数字，用递归实现排列的添加，外层的for实现了回溯功能；

用纸笔走过一遍后基本在一段时间内这段代码的影子都会在你的脑海里若隐若现

需要注意的问题：

当数字排满当前列表添加到二维列表的时候，应当new一个列表才能成功add进去总列表。

permutations.add(new ArrayList<>(current));

因为在递归的过程中，current当前列表会不断变化，他是列表对象，对象是存储在堆区里的，所以它会一直指向一个current对象，导致add失败；

但是current列表add整数是没关系的

current.add(nums[i]); //添加数字

因为整数是基本类型，基本类型存储在栈区，所以就是复制了整数值add进了current当前列表中。

全排列递归交换实现回溯 （抽象但更简单）

static void permute(int[] nums, int start, List<String> list) {
        if (start == nums.length - 1) {
            list.add(Arrays.toString(nums));
        } else {
            for (int i = start; i < nums.length; i++) {
                swap(nums, start, i);
                permute(nums, start + 1, list);
                swap(nums, start, i);
            }
        }
    }

    static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

拿什么容器什么类型装都是可以的，看具体需求具体实现。

本来想画图说明一下的，但是画的太丑，怕更混乱了。

拿纸和笔实现一下，你会发现递归回溯设计的很巧妙  :)

实战一下

洛谷  ---> P1088 [NOIP2004 普及组] 火星人   (普及-)

链接 P1088 [NOIP2004 普及组] 火星人 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)icon-default.png?t=N7T8https://www.luogu.com.cn/problem/P1088

是不是一眼看过去就有全排列的气息弥漫~ 

第一次尝试：

我们先把火星人给出的手指序号进行排序，然后用全排列出来（是呈字典序的），最后在原来手指序号的位置加上科学家给的数字，打印出这个位置的全排列数组。


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

public class 火星人 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int a = sc.nextInt();
        int[] init = new int[N];
        for (int i = 0; i < N; i++) {
            init[i] = sc.nextInt();
        }
        int[] nums = init;
        Arrays.sort(nums);
        List<String> list = new ArrayList<>();
        permute(nums, 0, list);
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
        	if(init.toString().equals(list.get(i).toString())) {
        		index = i;
        		break;
        	}
		}
        
        char[] c = list.get(index+a).toCharArray();
        for (int i = 1; i < c.length; i+=3) {
			System.out.print(c[i]+ " " );
		}
    }

    static void permute(int[] nums, int start, List<String> list) {
        if (start == nums.length - 1) {
            list.add(Arrays.toString(nums));
        } else {
            for (int i = start; i < nums.length; i++) {
                swap(nums, start, i);
                permute(nums, start + 1, list);
                swap(nums, start, i);
            }
        }
    }

    static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

好像用C++这种方法貌似过了。但是java没过，超空间超时了。

-----------------------------------------------------

第N次尝试：

不生成所有的排列组合，而是通过寻找下一个排列的方式逐个生成，并在满足条件时提前结束循环。这样可以避免生成不必要的排列组合，减少计算量。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class 火星人 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int a = sc.nextInt();
        int[] init = new int[N];
        for (int i = 0; i < N; i++) {
            init[i] = sc.nextInt();
        }
        int[] nums = init.clone();
        Arrays.sort(nums);

        List<String> list = new ArrayList<>();
        permute(nums, a, list);

        char[] c = list.get(a).toCharArray();
        for (int i = 1; i < c.length; i += 3) {
            System.out.print(c[i] + " ");
        }
    }

    static void permute(int[] nums, int a, List<String> list) {
        list.add(Arrays.toString(nums));

        while (a > 0) {
            int i = nums.length - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]) {
                i--;
            }

            if (i < 0) {
                break;
            }

            int j = nums.length - 1;
            while (j > i && nums[j] <= nums[i]) {
                j--;
            }

            swap(nums, i, j);
            reverse(nums, i + 1);

            list.add(Arrays.toString(nums));
            a--;
        }
        
    }

    //实现swap方法
    static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    //双指针实现翻转数组
    static void reverse(int[] nums, int start) {
        int end = nums.length - 1;
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

好好好，还是只过了一个。

我宣布实战失败，举一并不能反一，投降了。 

-----------------

# 算法 # 数据结构 # java # 推荐算法 # 迭代加深
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

avatar 开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

avatar 开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

avatar 开放原子开发者工作坊