全排列的概念

排列

从n个数中选取m（m<=n）个数按照一定的顺序进行排成一个列，叫作从n个元素中取m个元素的一个排列。不同的顺序是一个不同的排列。从n个元素中取m个元素的所有排列的个数，称为排列数（几种排法）。

全排列

从n个元素取出n个元素的一个排列，称为一个全排列。全排列的排列数公式为 n！

时间复杂度

n个数的全排列有n!种，每一个排列都有n个数据，所以输出的时间复杂度为O(n*n!)，呈指数级，无法处理大型数据。

一、逐步生成大法——迭代（递推）法

三层for循环

第一层：从第二个字符开始遍历

第二层：访问上一趟集合数组中的每一个字符串，然后给每个字符串前面、后面插入字符

第三层：往字符串中间插入字符

需要额外集合

import java.util.ArrayList;
import java.util.Scanner;public class Main {public static void main(String[] args) {String s = "abc";ArrayList<String> res = getPermutation(s);System.out.println(res);}public static ArrayList<String> getPermutation(String s){ArrayList<String> res = new ArrayList<>();//创建集合，用来迭代res.add(s.charAt(0)+"");//初始化集合，添加第一个元素，包含第一个字符for(int i=1;i<s.length();i++){char c = s.charAt(i);//从第二个字符开始插入集合字符串元素，每插入一个就形成一个新字符串ArrayList<String> new_res = new ArrayList<>();//创建临时集合，用来存储新生成的字符串for(String str:res){//遍历上一趟迭代结果集合中的每一个字符串String newStr = c + str;//插入前面new_res.add(newStr);newStr = str + c;//插入后面new_res.add(newStr);for(int j=1;j<str.length();j++){newStr = str.substring(0,j) + c + str.substring(j);//插入中间new_res.add(newStr);}}res = new_res;//本次迭代结果作为下一次迭代初始值}return res;//返回最后结果}
}

二、递归

跟上面的递推有一点像，需要额外集合

import java.util.ArrayList;
import java.util.Scanner;public class Main {public static void main(String[] args) {String s = "abc";int n = s.length();ArrayList<String> res = getPermutation(s, n);System.out.println(res);}public static ArrayList<String> getPermutation(String s, int n) {ArrayList<String> res = new ArrayList<>();//创建集合，用来存储第一个元素，用于递归终止if (n == 1) {//递归终止条件res.add(s.charAt(0) + "");//初始化，把a添加进去return res;//返回初始集合} else {ArrayList<String> res1 = getPermutation(s, n - 1);//创建集合，用于存储上一趟迭代的结果，为了不重复本地变量,命名为res1，代替reschar c = s.charAt(n - 1);ArrayList<String> new_res = new ArrayList<>();//创建临时集合，用于存储新生成的字符串for (String str : res1) {String newStr = c + str;//加前new_res.add(newStr);newStr = str + c;//加后new_res.add(newStr);for (int j = 1; j < str.length(); j++) {//加中间newStr = str.substring(0, j) + c + str.substring(j);new_res.add(newStr);}}res1 = new_res;//更新res1，把迭代结果赋值给res1return res1;//返回迭代结果}}
}

三、回溯法（或交换法）不在乎顺序的情况下,只求全排列

特点：代码简洁、处理重复（字符）自然、非字典序（，如果需要字典序则在最后对字符串集合进行一次排序 Collections.sort( ) ）、不需要额外集合（因为是对同一个数组空间操作）

三个思维难点：

在for循环内进行多路（多分支）递归，递归先执行完毕
先纵后横
需要回溯，恢复至最初状态，abc，因为共享存储空间，每次都是对同一个数组进行修改，每次都要从根节点abc开始向下层逐层递归

画图理解：

程序大致流程：比如第一支分路，先确定 a 从 a 开始，往下递归，再依次确定 b 和 c ，到达边界条件，把当前数组情况 abc，存入集合。再回溯，恢复交换前的状态（abc），因为 k=1 时，for循环还未执行完，进行第二轮，交换 b、c位置，确定了 c ，往下递归，k=2 时，确定了 b ，到达边界条件，把当前数组情况 acb 存入集合，再次逐层回溯，直到恢复初始 abc ，再进行第二路分支......

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;public class Main {public static void main(String[] args) {String s = "abc";ArrayList<String> res = new Main().getPermutation(s);//赋值给resSystem.out.println(res);}ArrayList<String> res = new ArrayList<>();// 创建集合public ArrayList<String> getPermutation(String q) {char[] c = q.toCharArray();Arrays.sort(c);getPermutationCore(c, 0);// 调用核心递归方法求解//Collections.sort(res);//对集合进行排序，字典序return res;// 集合}private void getPermutationCore(char[] c, int k) {// 核心递归方法if (k == c.length) {// 完成一种排列情况，存入集合res.add(new String(c));}for (int i = k; i < c.length; i++) {swap(c, k, i);// 交换getPermutationCore(c, k + 1);// 递归至下一层swap(c, k, i);//在回溯到上一层之前，给换回来，到最顶层时恢复成abc7  }}static void swap(char[] c, int i, int j) {// 交换字符元素char temp = c[i];c[i] = c[j];c[j] = temp;}
}

不排序，输出结果为：

[abc, acb, bac, bca, cba, cab]

排序，按照字典序，输出结果为：

[abc, acb, bac, bca, cab, cba]

四、前缀法求第k个排列

特点：复杂（代码量多）、处理重复（字符）较差（需要进行判断）、字典序（处理较好，每次加的是字符集中未加入字符字典序最小的那个字符）

对于求第k个排列来说，可以使用交换法求出所有的排列，然后对所有排列进行排序，从而解出第k个排列，但是这样的做法不节省时间和空间，没效率。实际上可以按序求出排列，直到求出第k个排列，然后返回就行了。

大致流程：从头开始扫描字符集abc，（把字符加入前缀中之前先判断是否已经加入过）把a加入前缀，直到完成一中排列abc，直到退回上上层ab，此时循环未执行完，进入下一轮循环，把c加入进来，变成ac......

需要额外处理重复的字符

import java.util.ArrayList;
import java.util.Arrays;public class Main {public static void main(String[] args) {String s = "123";getPermutation("", s.toCharArray());}final static int k = 3;// 第k个排列static int count = 0;// 记录排列完成次数private static void getPermutation(String prefix, char[] arr) {if (prefix.length() == arr.length) {// 边界条件：前缀的长度==字符集的长度，一个排列就完成了count++;if (count == k) {// 程序结束条件System.out.println(prefix);// 输出目标排列System.exit(0);// 正常退出，结束当前正在运行的java虚拟机}}// 每次都从头扫描字符集，只要该字符可用(可添加)，我们就附加到前缀后面，前缀变长了for (int i = 0; i < arr.length; i++) {char ch = arr[i];// 处理重复字符。这个字符可用：在prefix中出现的次数 < 在字符集中出现的次数if (count(prefix, ch) < count(arr, ch)) {getPermutation(prefix + ch, arr);// 把字符加入前缀，进行递归}}}private static int count(String prefix, char ch) {// 计算当前字符在前缀prefix中出现的次数int cnt = 0;for (int i = 0; i < prefix.length(); i++) {if (prefix.charAt(i) == ch) {cnt++;}}return cnt;}private static int count(char[] arr, char ch) {// 计算当前字符在字符集中出现的次数int cnt = 0;for (int i = 0; i < arr.length; i++) {if (arr[i] == ch) {cnt++;}}return cnt;}
}

输出：213