首页 > 代码库 > 全排列的几种算法
全排列的几种算法
全排列，我们高中时就学过，数学上很简单，可是用计算机的算法实现还是有点味道的，
今天我将我碰到的几种算法如数奉上，欢迎交流！
第一种：递归
最常见的也是最好理解的方法：
简单点：比如"a" ,"b","c"全排列，可以看做事"a" +"b","c"的全排列 及"b"+ "a","c"的全排列 及"c" + "a","b"的全排列
也就是说，遍历原数组中的每个元素，让剩余的元素全排列，这样就找到规律了。
代码如下：
public static void main(String[] args) { char buf[]={‘a‘,‘b‘,‘c‘,‘d‘}; perm(buf,0,buf.length-1); } public static void perm(char[] buf,int start,int end){ if(start==end){//当只要求对数组中一个字母进行全排列时，只要就按该数组输出即可（特殊情况） for(int i=0;i<=end;i++){ System.out.print(buf[i]); } System.out.println(); } else{//多个字母全排列（普遍情况） for(int i=start;i<=end;i++){//（让指针start分别指向每一个数） char temp=buf[start];//交换数组第一个元素与后续的元素 buf[start]=buf[i]; buf[i]=temp; perm(buf,start+1,end);//后续元素递归全排列 temp=buf[start];//将交换后的数组还原 buf[start]=buf[i]; buf[i]=temp; } } }
第二中方法：也是递归，
但是和第一种有所区别，
算法：将数据分为两部分，递归将数据从左侧移右侧实现全排列
比较抽象，
如list abcd，遍历每一个数，将每个数放到一个新的list中,并将该元素从原list删除，然后将剩下的元素继续遍历每个元素继续放到新的list里，这样，当list的长度为原list长度，或者原list长度为0时打印结果！
下面是简单的示意图：
// abcd //bcd a //cd ab //d abc //abcd //c abd //abdc //bd ac //d acb //acbd //b acd //acdb //bc ad ... //acd b ... //abd c ... //abc d ...
源代码如下：
private static void sort(List datas, List target) { //System.out.println("size="+datas.size()); if (datas.size()==0) { for (Object obj : target) System.out.print(obj+" "); System.out.print(" "); return; } for (int i = 0; i < datas.size(); i++) { List newDatas = new ArrayList(datas); List newTarget = new ArrayList(target); newTarget.add(newDatas.get(i)); newDatas.remove(i); sort(newDatas, newTarget); } } public static void main(String[] args) { List list = new ArrayList(); for(int i=0;i<5;i++){ list.add(i+1); } sort(list, new ArrayList()); }
第三种方法：非递归
直接上代码：
public static void main(String[] args) { int[] arr = new int[]{1,2,3,4,5,6}; for(int i :arr){ System.out.print(i + " "); } System.out.println(); int totalnum = 1; while(NextNumber(arr,arr.length)){ for(int i :arr){ System.out.print(i + " "); } System.out.println(); totalnum ++; } System.out.println("Total Num: " + totalnum); } private static Boolean NextNumber(int[] arr, int n){ //数组最后一个元素位置 int lastIndex = n-1; //从右向左确定第一个数字（前面的数字比它小） int firstIndex = lastIndex; for(;arr[firstIndex-1]>arr[firstIndex];firstIndex--){ if(firstIndex == 1){ //已经轮询完毕,此数已经是最大的那个数 return false; } } //从右向左确定一个交换数（此数比arr[firstIndex]小且比arr[firstIndex-1]大） int swapIndex = lastIndex; for(;swapIndex > firstIndex;swapIndex--){ if(arr[swapIndex] < arr[firstIndex] && arr[swapIndex] > arr[firstIndex-1]){ break; } } //交换数字 swap(arr,firstIndex-1,swapIndex); //将firstIndex右边的数字排序 for(;firstIndex < lastIndex;firstIndex++,lastIndex--){ if(arr[firstIndex] > arr[lastIndex]){ swap(arr,firstIndex,lastIndex); } } return true; } private static void swap(int[] arr,int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }
如果此文对你有帮助，请留个言，新人需要打架的支持和鼓励！
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。