全排列算法的递归与非递归实现

全排列算法的递归与非递归实现（java版）

---

问题定义

对于给定的集合A{a1,a2,…,an},其中的n个元素互不相同，如何输出这n个元素的所有排列（全排列）。
例如：给定集合[1,2,3] 它的全排列子集为：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

递归算法（非去重）

思路：
1.保持第一个数不变，对后面的数进行全排列
2.将第一个数换成其它数，对后面的数进行全排列
3.第一个数所有情况遍历遍历完成，得到全排列
例如：【1，2，3，4】
对1开头的所有排列，得到【1，2，3，4】【1，2，4，3】【1，3，2，4】【1，3，4，2】【1，4，2，3】【1，4，3，2】
对2开头的所有排列….依次类推

 public List<List<Integer>> permute(int[] nums) {
        // write your code here
        List<List<Integer>> result=new ArrayList<>();
        List<Integer> permutation=new ArrayList<>();
        Set<Integer> set=new HashSet<>();
        if(nums==null){
            return result;
        }
         if(nums.length==0){
             result.add(new ArrayList<Integer>());
             return result;
        }

        Helper(nums,permutation,set,result);
        return result;
    }

    public void Helper(int[] nums,List<Integer> permutation,
          Set<Integer> set,List<List<Integer>> result){
        if(permutation.size()==nums.length){
            result.add(new ArrayList<Integer>(permutation));//???
            return;
        }

        for(int i=0;i<nums.length;i++){
            if(permutation.contains(nums[i]))
               continue;
            permutation.add(nums[i]);
            set.add(nums[i]);
            Helper(nums,permutation,set,result);
            set.remove(nums[i]);
            permutation.remove(permutation.size()-1);
        }

    }

注意：此方法对于有重复元素的集合无效
为什么需要两个集合来保存数据？
1.list不适合随机存取，适合顺序存取，remove(index)
2.list适合随机存取，不适合遍历，remove(value)
3.IndexOutOfBoundsException错误提醒我们：使用remove()的方法时，要先从大到小的位置移除。当然如果你知道具体的对象，直接移除remove(对象)更稳妥。

非递归算法（按字典序排列算法）

思路：
1.对初始队列进行排序，找到所有排列中最小的一个排列Pmin。
2.找到刚刚好比Pmin大比其它都小的排列P(min+1)。
3.循环执行第二步,直到找到一个最大的排列,算法结束。
如排列12345，这是所有排列中最小的一个排列，刚好比12345大的排列是：12354。

算法如下：
给定已知序列P = A1A2A3…..An
对P按字典排序，得到P的一个最小排列Pmin = A1A2A3….An ，满足Ai > A(i-1) (1 < i <= n)
从Pmin开始,找到刚好比Pmin大的一个排列P(min+1)，再找到刚好比P(min+1)大的一个排列，如此重复。
1.从后向前（即从An->A1）,找到第一对为升序的相邻元素，即Ai < A(i+1)。
若找不到这样的Ai，说明已经找到最后一个全排列，可以返回了。
2.从后向前,找到第一个比Ai大的数Aj，交换Ai和Aj。
3.将排列中A(i+1)A(i+2)….An这个序列的数逆序倒置，即An…..A(i+2)A(i+1)。因为由前面第1、2可以得知，A(i+1)>=A(i+2)>=…..>=An,这为一个升序序列，应将该序列逆序倒置，所得到的新排列才刚刚好比上个排列大。
4.重复步骤1-3,直到返回。
这个算法是C++ STL算法next_permutation的思想。
（盗来的图，哈哈哈）

public List<List<Integer>> permuteUnique(int[] nums) {
        // write your code here       
         List<List<Integer>> list=new ArrayList<>();
        if(nums==null|nums.length == 0){
            list.add(new ArrayList<Integer>());
            return list;
        }
          //排序
        insertionSort(nums);        
        List<Integer> array= new ArrayList<Integer>();
        for (int t : nums)
        {
            array.add(t);
        }
        list.add(array);    
        int i;
        while((i=hasNext(nums))>0){
            int a=nums[i-1];
            int b=nums[i];
            int k=i;
            int j=i;
            while(j<nums.length){
                if(nums[j]>a & nums[j]<=b){
                    b=nums[j];
                    k=j;
                }
                j++;
            }
            swap(nums,i-1,k);
            //反转
            reverse(nums,i,nums.length-1);
            List<Integer> arr= new ArrayList<Integer>();
            for (int t : nums)
            {
                arr.add(t);
            }
            list.add(arr);
        }
        return list;
    }
    public int hasNext(int[] nums){
        for(int i=nums.length-1;i>0;i--){
            if(nums[i]>nums[i-1]){
                return i;
            }
        }
        return 0;
    }
    public void reverse(int[] nums,int i,int j){
        while(i<j){
            swap(nums,i++,j--);
        }
    }
    public void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
        return ;
    }
    public void insertionSort(int[] arr) {
    int len = arr.length;
    int preIndex, current;
    for (int i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
     }    
    }

如果元素集合不方便比较 可以将它们在数组中的索引作为元素

使用字典序输出集合的全排列需要注意，因为字典序涉及两个排列之间的比较，对于元素集合不方便比较的情况，可以将它们在数组中的索引作为元素，按照字典序生成索引的全排列，然后按照索引输出对应集合元素的排列，示例代码使用的就是此方法。对于集合A{a,b,c,d}，可以对其索引1234进行全排列生成。这么做还有一个好处，就是对于字典序全排列生成算法，需要从字典序最小的排列开始才能够生成集合的所有排列，如果原始集合A中的元素不是有序的情况，字典序法将无法得到所有的排列结果，需要对原集合排序之后再执行生成算法，生成索引的全排列，避免了对原始集合的排序操作。

需要先排序好，不受重复元素影响

字典序算法还有一个优点，就是不受重复元素的影响。例如1224，交换中间的两个2，实际上得到的还是同一个排列，而字典序则是严格按照排列元素的大小关系来生成的。对于包含重复元素的输入集合，需要先将相同的元素放在一起，以集合A{a,d,b,c,d,b}为例，如果直接对其索引123456进行全排列，将不会得到想要的结果，这里将重复的元素放到相邻的位置，不同元素之间不一定有序，得到排列A’{a,d,d,b,b,c}，然后将不同的元素，对应不同的索引值，生成索引排列122334，再执行全排列算法，即可得到最终结果。