Next Permutation
Permutations
Permutations II

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

总共分为三步：

倒序遍历数组，直到找到nums[i] < nums[i+1]。 e.g. nums[5] = {1, 3, 5, 4, 2} -> i = 1.
此时可以确保i位后的数都是降序的，再次在(i, N)范围内找到nums[j] > nums[i]，然后交换ij位置的数。 e.g. j = 3 -> nums[5] = {1, 4, 5, 3, 2}.

将i位之后的数重新按升序排列。 e.g. nums[5] = {1, 4, 2, 3, 5}.

public void nextPermutation(int[] nums) {
    if (nums.length < 2)
        return;
        
    int i = nums.length-2;
    for (; i >= 0; i--)
        if (nums[i + 1] > nums[i])
            break;
         
    if (i == -1)
        Arrays.sort(nums);
    else {
        int left = i+1, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= nums[i]) 
                right = mid - 1;
            else 
                left = mid + 1;
        }
        int temp = nums[right];
        nums[right] = nums[i];
        nums[i] = temp;
        Arrays.sort(nums, i+1, nums.length);
    }
}

注意Arrays.sort()函数只能升序排列，没有降序排列。

无重复全排序

#46 Permutations

Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

一全部遍历

对于长度为n的数组，对于每一位，都有n种选择。
用递归实现，确定第一位的元素(n个选择)，然后对之后的做递归进行全排序。
对于每一位都遍历n个元素，先判断该元素前面是否已经存在，若不存在，则加入，否则跳过。
复杂度O(n^n)

public List<List<Integer>> permute(int[] nums) {
          List<List<Integer>> list = new ArrayList<List<Integer>>();
          List<Integer> p = new ArrayList<Integer>();
          recurPermute(p,nums, 0, list);
          return list;
   }
   
   public void recurPermute(List<Integer> p, int[] nums, int cur, List<List<Integer>> list) {
       if (cur == nums.length)
           list.add(new ArrayList<Integer>(p));
       else {
           for (int i = 0; i < nums.length; i++) {
               if (!p.contains(new Integer(nums[i]))) {
                   p.add(nums[i]);
                   recurPermute(p, nums, cur+1, list);
                   p.remove(cur);
               }
           }
       }
   }

二交换

将每一位都与每一位做交换(包括自己)，在一次交换后，再对后面的数组做递归操作。
结构如下
↓

0                      1234
                    /  |  \  \
                   /   |   \  \ 
                  /    |    \  \
1             1234    2134 3214 4231
           /    |    \
          /     |     \
2     1234    1324     1432
     / \       / \      / \
3 1234 1243 1324 1342 1432 1423

public List<List<Integer>> permute(int[] nums) {
       List<List<Integer>> list = new ArrayList<List<Integer>>();
       recurPermute(list, nums, 0);
       return list;
   }
   
   public void recurPermute(List<List<Integer>> list, int[] nums, int cur) {
       if (cur == nums.length) {
           Integer[] res = new Integer[nums.length];
           int i = 0;
           for (int value : nums)
               res[i++] = Integer.valueOf(value);
           list.add(Arrays.asList(res));
       }
       
       for (int i = cur; i < nums.length; i++) {
           swap(nums, cur, i);
           recurPermute(list, nums, cur+1);
           swap(nums, cur, i);
       }
   }
   
   public void swap(int[] nums, int i, int j)  {
       int temp = nums[i];
       nums[i] = nums[j];
       nums[j] = temp;
   }

注意int数组不能直接用asList放入list中，这样产生的是List，而不是List，要先转换为Integer对象。

三插空

开始时是一个空数组，可以往里面插入一个数。然后插第二个数，可以插在第一数的前面或后面。同理第三个数有三个空位可以插入。……

[1]
[1, 2], [2, 1]
[1, 2, 3], [1, 3, 2], [3, 1, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1]
...

四利用Next Permutation

先将数组顺序排列，然后调用next permutation函数，直到permutation最大结束。

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    Arrays.sort(nums);
    do {
        Integer[] res = new Integer[nums.length];
        int index = 0;
        for (int value : nums)
            res[index++] = value;
        list.add(Arrays.asList(res));
    } while (nextPermutation(nums));
    
    return list;
}

public boolean nextPermutation(int[] nums) {
    if (nums.length < 2)
        return false;
        
    int i = nums.length-2;
    for (; i >= 0; i--)
        if (nums[i + 1] > nums[i])
            break;
         
    if (i == -1) {
        return false;
    }
    else {
        int left = i+1, right = nums.length-1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= nums[i]) 
                right = mid - 1;
            else 
                left = mid + 1;
        }
        int temp = nums[right];
        nums[right] = nums[i];
        nums[i] = temp;
        Arrays.sort(nums, i+1, nums.length);
        return true;
    }
}

有重复全排序

#47 Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

基于上面无重复排序的二交换部分。
在进行交换时，需要增加一个判断条件，即对于nums[i] 和 nums[j] (i < j)，需要判断nums[j]是否已在[i,j)区间中出现过。若没有，则正常交换，否则不能交换。

public List<List<Integer>> permuteUnique(int[] nums) {
       List<List<Integer>> list = new ArrayList<List<Integer>>();
       recurPermute(list, nums, 0);
       return list;
   }
   
   public void recurPermute(List<List<Integer>> list, int[] nums, int cur) {
       if (cur == nums.length) {
           Integer[] res = new Integer[nums.length];
           int i = 0;
           for (int value : nums)
               res[i++] = Integer.valueOf(value);
           list.add(Arrays.asList(res));
       }
       for (int i = cur; i < nums.length; i++) {
           if (isRepeated(nums, cur, i))
               continue;
           swap(nums, cur, i);
           recurPermute(list, nums, cur+1);
           swap(nums, cur, i);
       }
   }
   
   public boolean isRepeated(int[] nums, int left, int right) {
       while (left < right)
           if (nums[left++] == nums[right])
               return true;
       return false;
   }
   
   public void swap(int[] nums, int i, int j) {
       int temp = nums[i];
       nums[i] = nums[j];
       nums[j] = temp;
   }

Next Permutation

无重复全排序

一 全部遍历

二 交换

三 插空

四 利用Next Permutation

有重复全排序

一全部遍历

二交换

三插空

四利用Next Permutation