Permutation总结

有关排列的问题我们可以与组合比较来考虑，解决这类问题我们都采用回溯法，在组合中不用考虑顺序，而在排列中就要考虑顺序，例如（1，2，3）和（2，1，3），在组合的概念中是相等的，但它们是不同的排列。下面列举leetcode中有关permutations的几道题目。

1，Permutation
给定一个数组numbers ，输出所有可能的排列。
例如：numbers = {1，2，3}；
输出：[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2],[3,2,1].

因为我们要考虑顺序，回溯的时候我们始终从第一个元素开始遍历，如果长度等于数组的长度我们就找到结果，保存这个结果，然后返回上一层，继续遍历。代码如下：

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        LinkedList<Integer> list = new LinkedList<Integer>();
        if(nums == null) return llist;
        permutation(0, nums, list, llist);
        return llist;
    }
    
    private void permutation(int start, int[] nums, LinkedList<Integer> list, List<List<Integer>> llist) {
        if(list.size() == nums.length){
            llist.add(new LinkedList<Integer>(list));
        }
        for(int i = start; i < nums.length; i++) {
            if(list.size() < nums.length && !list.contains(nums[i])) {
                list.add(nums[i]);
                permutation(0, nums, list, llist);
                list.removeLast();
            }
        }
    }
}

2，Permutation2
给定一个数组numbers, 给出所有可能的排列，数组中可能存在重复元素。
例如：numbers[] = {1,1,2}
输出：[1,1,2], [1,2,1], [2,1,1].

因为有重复元素，所以在判断添加元素时不能通过元素的值来判断，我们可以通过维护一个数组，来记录已经遍历过的元素的下标，只添加没遍历过的元素。代码如下：

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> llist = new ArrayList<List<Integer>>();
        LinkedList<Integer> list = new LinkedList<Integer>();
        LinkedList<Integer> usedIndex = new LinkedList<Integer>();
        if(nums == null) return llist;
        Arrays.sort(nums);
        permutationUnique(0, nums, list, usedIndex, llist);
        return llist;
    }
    
    private void permutationUnique(int start, int[] nums, LinkedList<Integer> list, LinkedList<Integer> usedIndex, List<List<Integer>> llist) {
        if(list.size() == nums.length) {
            llist.add(new LinkedList<Integer>(list));
        }
        int delete = Integer.MAX_VALUE;
        for(int i = start; i < nums.length; i++) {
            if(delete == nums[i]) continue;
            if(!usedIndex.contains(i)) {
                usedIndex.add(i);
                list.add(nums[i]);
                permutationUnique(0, nums, list, usedIndex, llist);
                usedIndex.removeLast();
                delete = list.removeLast();
            }
        }
    }
}

3，Next Permutation
给定一个排列，返回下一个比它大的排列。如果找不到比它大的元素，就返回排列中和最小的组合。
例如：
给定1, 2, 3  返回 1, 3, 2
给定3, 2, 1 返回 1, 2, 3
给定 1, 1, 5 返回 1, 5, 1

找到比它大的组合，我们不妨从后面遍历数组，找到第一个i元素，使nums[i] >nums[i-1], 找到这个位置如果直接将它们位置调换并不一定不符合提议，例如一个数组是{1，2，5，3}，第一个nums[i] >nums[i-1] 的是5>2，如果直接将它们交换结果为{1，5，2，3}，而正确结果应该为{1，3，2，5}。因此再找到这个i位置后，我们要遍历i元素后面的元素，如果有元素比nums[i-1]
大，就将它们位置互换，再将i后面剩余的元素按升序排列。实现代码如下：

public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums == null) return;
        for(int i = nums.length - 1; i > 0; i--) {
            if(nums[i] > nums[i-1]) {
                int j = nums.length - 1;
                while(j > i-1 && nums[j] <= nums[i-1]) j --;
                int tem = nums[i-1];
                nums[i-1] = nums[j];
                nums[j] = tem;
                Arrays.sort(nums, i, nums.length);
                return;
            }
        }
        reverse(nums);  
    }
    
    public void reverse(int[] nums) {
        int l = 0;
        int r = nums.length -1;
        while(l < r) {
            int tem = nums[l];
            nums[l] = nums[r];
            nums[r] = tem;
            l ++;
            r --;
        }
    }
}

4，Permutation Sequence
给定一个整数n，n >= 1 && n <= 9; 在给定一个整数k，要求输出第k个排列。

如果我们用回溯法列出所有排列，然后取第k个排列。代码如下：

public class Solution {
   
    List<List<Integer>> llist = new ArrayList<List<Integer>>();
    
    public String getPermutation(int n, int k) {
        List<Integer> list = new ArrayList<Integer>();
        if(n == 0) return null;
        permutation( n, k, list);
        if(k <= llist.size()){
            String result = "";
            for(int i = 0; i < llist.get(k-1).size(); i++){
                result += llist.get(k-1).get(i).toString();
            }
            return result;
        }
             
        return null;
    }
    private void permutation( int n, int k, List<Integer> list){
        if(list.size() == n) {
            llist.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i = 1; i <= n; i++){
            if(!list.contains(i)) {
                list.add(i);
                permutation(n, k, list);
                list.remove(list.size()-1);
            }
        }
    }
}

到这样会超时，我们完全可以直接计算出第k个排列。我们都知道n个元素全排列的结果为n！，我们把这n！个排列分成n组，每个组都有（n-1）!个，那么第k个元素在第几组呢，我们不妨通过简单的例子来分析一下，当n = 3时，第一组为{1，2，3}，{1，3，2}； 第二组为{2，1，3}，{2，3，1} ；第三组为{3，1，2}，{3，2，1}，因此当k等于1或2时属于第一组；等于3，4时属于第二组；等于5，6时属于第三组，符合(k-1)%(n-1)! ，这样我们就确定了第一个元素。我们令k = k/(n-1)!，循环操作，直到n为1位置，代码如下：

public class Solution {
    public String getPermutation(int n, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        StringBuffer sb = new StringBuffer();
        int[] fac = new int[n];
        fac[0] = 1;
        for(int i = 1; i < n; i++) {
            fac[i] = fac[i-1] * i;
        }
        
        for(int i = 1; i <= n; i++) {
            list.add(i);
        }
        
        k = k - 1;
        for(int i = 0; i <= n - 1; i++) {
            int index = k /fac[n - 1 - i];
            sb.append(list.get(index));
            list.remove(index);
            k = k % fac[n - 1 - i];
        }
        return sb.toString();
    }
}