更多解释可参考关于递归求法的图解递归算法/** * 1、递归算法 * * 有重复值 * 由于全排列就是从第一个数字起每个数分别与它后面的数字交换我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。 * 例如abb第一个数与后面两个数交换得babbba。然后abb中第二个数和第三个数相同就不用交换了。 * 但是对bab第二个数和第三个数不 同则需要交换得到bba。 * 由于这里的bba和开始第一个数与第三个数交换的结果相同了因此这个方法不行。 * * 换种思维对abb第一个数a与第二个数b交换得到bab然后考虑第一个数与第三个数交换此时由于第三个数等于第二个数 * 所以第一个数就不再用与第三个数交换了。再考虑bab它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕 * param str * return */publicArrayListStringpermutation(String str){ArrayListStringlistnewArrayList();//存放排列后的字符串if(str!nullstr.length()0){permutationHelper(str.toCharArray(),0,list);Collections.sort(list);//排序list中的元素}returnlist;}privatevoidpermutationHelper(char[]chars,inti,ArrayListStringlist){if(ichars.length-1){list.add(String.valueOf(chars));//当交换到最后一个字符时将对应的字符串添加到list中}else{SetCharactercharSetnewHashSet();for(intji;jchars.length;j){if(ji||!charSet.contains(chars[j])){//排除字符串中具有相同字符的交换、递归charSet.add(chars[j]);swap(chars,j,i);permutationHelper(chars,i1,list);//注意此次的时i1而不是i。swap(chars,j,i);}}}}privatevoidswap(char[]cs,inti,intj){chartempcs[i];cs[i]cs[j];cs[j]temp;}字典序排列算法/** * 2、字典序排列算法 * * 可参考解析 http://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html 感谢作者 * * 一个全排列可看做一个字符串字符串可有前缀、后缀。 * 生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。 * 这就要求这一个与下一个有尽可能长的共同前缀也即变化限制在尽可能短的后缀上。 * * [例]839647521是1--9的排列。1—9的排列最前面的是123456789最后面的987654321 * 从右向左扫描若都是增的就到了987654321也就没有下一个了。否则找出第一次出现下降的位置。 * * 【例】 如何得到346987521的下一个 * 1从尾部往前找第一个P(i-1) P(i)的位置 * 3 4 6 - 9 - 8 - 7 - 5 - 2 - 1 * 最终找到6是第一个变小的数字记录下6的位置i-1 * * 2从i位置往后找到最后一个大于6的数 * 3 4 6 - 9 - 8 - 7 5 2 1 * 最终找到7的位置记录位置为m * * 3交换位置i-1和m的值 * 3 4 7 9 8 6 5 2 1 * 4倒序i位置后的所有数据 * 3 4 7 1 2 5 6 8 9 * 则347125689为346987521的下一个排列 * * param str * return */ public ArrayListString Permutation2(String str){ ArrayListString list new ArrayListString(); if(strnull || str.length()0){ return list; } char[] chars str.toCharArray(); Arrays.sort(chars); list.add(String.valueOf(chars)); int len chars.length; while(true){ int lIndex len-1; int rIndex; while(lIndex1 chars[lIndex-1]chars[lIndex]){ lIndex--; } if(lIndex 0) break; rIndex lIndex; while(rIndexlen chars[rIndex]chars[lIndex-1]){ rIndex; } swap(chars,lIndex-1,rIndex-1); reverse(chars,lIndex); list.add(String.valueOf(chars)); } return list; } private void reverse(char[] chars,int k){ if(charsnull || chars.lengthk) return; int len chars.length; for(int i0;i(len-k)/2;i){ int m ki; int n len-1-i; if(mn){ swap(chars,m,n); } } }