数字全排列返回list的list：java实现

朴灿烈づ我的快乐病毒、 2022-06-07 00:51 143阅读 0赞

程序实际很简单，是一个递归的过程。过程如下:

![20171001170643136][]

括号里是传进去的begin和end参数，而后面跟的数字是进入之后需要循环的次数。

这个程序也更让我理解了，递归程序的过程：

好比是一个人在执行任务，在执行过程中有很多分叉，如果有分叉的情况，就分叉的情况扔到栈中去，因为栈是先进后出的，所以用栈符合要求。同地位的分叉总有先后顺序，这个人走到第一个分叉的第一个分叉，一直到第一个到达的终点，到达终点后，到栈中去看分叉情况，如果还有分叉就继续执行到下一个终点。重点在于到了终点就返回上一层（返回到上一层调用的函数那行），完成上一层没有执行完的工作，如果上一层没事了，就看上一层的上一层，以此类推。

开始我有疑问，递归函数中，对数组的引用一直是同一个引用，但还一直在swap，这样能对吗？原来是每次循环中，最后一行又把交换的元素换回来了，这样就为下一次循环，即同地位的分叉做好了准备。

代码如下：

package mianshi;
    
    import java.util.ArrayList;
    import java.util.List;
    
    public class pailie {
    
    	public static List<List<Integer>> permute(int[] nums)
    	{
    		List<List<Integer>> all=new ArrayList<List<Integer>>();
    		allSort(nums, 0, nums.length-1, all);
    		return all;
    	}
    	public static void allSort(int[] array,int begin,int end,List<List<Integer>> all)
    	{
    		  if(begin==end){
    			    List<Integer> origi=new ArrayList<Integer>();
    				for(int a:array) 
    				{
    					origi.add(a);
    				}
    				all.add(origi);
    		        return;
    		    }
    		    
    		    for(int i=begin;i<=end;i++){
    		        swap(array,begin,i );
    		        allSort(array, begin+1, end,all);
    		        swap(array,begin,i );
    		    }
    
    	}
    	public static void swap(int[] array,int a,int b){
    	    int tem=array[a];
    	    array[a]=array[b];
    	    array[b]=tem;
    	}
    	
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
            int[] a={1,2,3,4};
            permute(a);
            for(List<Integer> b:permute(a))
            {
    
            	for(int c:b)
            	{
            		System.out.println(c);
            	}
            }
    	}
    
    }

[20171001170643136]: /images/20220607/e70b3d590c82452ebcc5c0f12c327c88.png