失眠网 > 【算法】全排列的四种思路

【算法】全排列的四种思路

时间：2023-12-19 18:54:09

相关推荐

【算法】全排列的四种思路

一、公式

n个元素全排列，有n!种排列方式。

即：f(n) = n!

二、实现思路及代码

思路一：头中尾插入法——单路递归

先对前n-1个字符全排列，得到全排列集合后，对集合中每个排列，第n个字符都可以往头插、往尾插、往中间插。

值得注意的是，往中间插的时候，是往该排列的每两个字符中间插，需遍历该排列。

/*** way01——插入法的迭代实现* @param str* @return*/public static ArrayList<String> getPermutation01(String str) {ArrayList<String> list = new ArrayList<>();// 1、初始化，装入第一个字符list.add(str.charAt(0) + "");// 2、把第2、3、4、、、n个字符插入到先前的序列集合中for (int i = 1; i < str.length(); i++) {ArrayList<String> temp = new ArrayList<>();char c = str.charAt(i);// 每个字母可以插在每个集合元素的前中后for (String s : list) {temp.add(c + s);//字符加在此序列的前面temp.add(s + c);//加在后面for (int j = 1; j < s.length(); j++) {//加在中间：插入在每个字母后面（除最后一个）String tt = s.substring(0,j) + c + s.substring(j);temp.add(tt);}}list = temp;//更新list}return list;}

/*** way02——插入法的递归实现* @param str 要全排列的字符串* @param n 排列前n个字符，包括n 初始：str.length* @return*/public static ArrayList<String> getPermutation02(String str, int n) {ArrayList<String> list = new ArrayList<>();// 1、出口if (n == 1) {list.add(str.charAt(0) + "");return list;}ArrayList<String> toList = getPermutation02(str,n-1);//取前包括一个字符前的的所有排列// 2、把第n个元素分前中后插入前n-1个字符的每个排列for (String e : toList) {list.add(str.charAt(n-1) + e);//插前list.add(e + str.charAt(n-1));//插后for (int i = 1; i < e.length(); i++) {//插中，遍历插在每个字母的后面，除最后一个String tt = e.substring(0,i) + str.charAt(n-1) + e.substring(i);list.add(tt);}}return list;}

思路二：抽丝法——多路递归，Sn = ai + Sn-1 (0 <= i <= n-1)

遍历取出第i个字符，对剩余字符进行全排列得到全排列集合，遍历集合，把第i个字符插到每一个全排列头部。

/*** way03——抽丝法* @param str* @return*/public static ArrayList<String> getPermutation03(String str) {ArrayList<String> list = new ArrayList<>();if (str.length() == 1) {list.add(str);return list;}char[] arr = str.toCharArray();//字符串》字符数组// 遍历字符数组，轮流取出每一个字符for (int i = 0; i < arr.length; i++) {// 对剩余字符全排列String ss;if (i < arr.length-1) ss = str.substring(0,i) + str.substring(i+1);else ss = str.substring(0,i);ArrayList<String> temp = getPermutation03(ss);for (int j = 0; j < temp.size(); j++) {String tt = arr[i] + temp.get(j);list.add(tt);}}return list;}

思路三：交换法——多路递归 + 交换回溯[经典]

遍历取出第i个字符，每次都与第一个字符交换位置，再对剩余字符进行遍历，取出第j个与剩余字符的第一个位置进行交换。

交换后注意回溯。（因为这里是原址交换，大家共享一个串空间，牵一发而动全身。每次到交换到分支叶节点后得回溯到原状态）

即：对从k位开始的每一个字符，都尝试放在新排列后的第k位的位置上。（k从0开始）

/*** way04——交换法* @param str* @param k 从第k位开始的每个字符，都尝试放在第k位上 (k从0开始）* @return*/static ArrayList<String> li = new ArrayList<>();public static ArrayList<String> getPermutation04(String str,int k) {char[] arr = str.toCharArray();//字符串》字符数组getPermutation04Core(arr,0);return li;}public static void getPermutation04Core(char[] arr,int k) {if (k == arr.length) {//递归的一个支路走到底了，则说明一个全排列排好了li.add(new String(arr));}// 从第k位开始的每个字符，都尝试放在第k位上for (int i = k; i < arr.length; i++) {swap(arr,i,k);//交换getPermutation04Core(arr,k+1);swap(arr,i,k);//回溯}}public static void swap(char[] A,int i,int j){char temp = A[i];A[i] = A[j];A[j] = temp;}

思路四：前缀法——可解决全排列字典序问题

核心：不断拼接前缀，直到长度＝字符数组长度。

完整思路：把字符串转为字符数组，先对字符数组排序，遍历字符数组，依次取出每一个可用字符与前缀拼接作为新的前缀，

再从头遍历字符数组，依次把可用的字符与新的前缀进行拼接，作为更新的前缀……直到前缀长度＝字符数组长度，一个全排列完成。

【注意】传进去的arr，需先排序。

/*** way05——前缀法字典序全排列问题* @param prefix* @param arr* @return*/static int count = 0;//统计出现了几个全排列public static void getPermutation05(String prefix,char[] arr) {// 前缀长度==arr长度，说明一个全排列完成if (prefix.length() == arr.length) {// System.out.println(prefix);count++;}// 遍历字符数组，轮流取出可用字符，加到前缀后面，作为新的前缀递归下去for (int i = 0; i < arr.length; i++) {// 判断当前字符是否可用——该字符在前缀中出现次数<字符数组中出现次数if (countCharTimes(prefix.toCharArray(),arr[i]) < countCharTimes(arr,arr[i])) {//prefix = prefix + arr[i];//ERROR: 不能拼接！！！，会改变前缀，影响后续循环getPermutation05(prefix + arr[i],arr);}}}/*** 统计在arr数组中字符c出现的次数* @param arr* @param c* @return*/public static int countCharTimes(char[] arr,char c) {int times = 0;for (int i = 0; i < arr.length; i++) {if (arr[i] == c) times++;}return times;}

例题：leetCode60 n个数的数列组合照出字典序的第k个排列

比较：

A、空间：插入法、抽私法都需要开辟额外ArrayList来存储子排列；交换法不需要额外的ArrayList，直接在数组上交换排列，节省空间；

B、时间：交换法<插入法<抽丝法

C、交换法和前缀法的比较：

交换法代码简洁，自然去重，但无法维持字典序。

前缀法代码较多，手动去重，能维持字典序。

使用场景：

A、若只需要求全排列——交换法（优）

B、若全排列要求字典序——前缀法

三、遇到的问题——堆溢出

堆溢出：