一、公式
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、若全排列要求字典序——前缀法
三、遇到的问题——堆溢出
堆溢出:
java.lang.OutOfMemoryError: Java heap space:
内存溢出java.lang.OutOfMemoryErrory后面一般会跟上内存溢出的区域。
PermGen space(方法区), heap space(堆内存)
解决方法:
1、如果是PermGen space方法区内存溢出,可尝试加大MaxPermSize
2、如果是heap space 堆内存溢出,可尝试修改Xmx
-Xms
设置JVM初始化堆内存大小
-Xmx
设置JVM最大的堆内存大小
如果觉得《【算法】全排列的四种思路》对你有帮助,请点赞、收藏,并留下你的观点哦!