Next Permutation @LeetCode

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

	package leetcode.combinations;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	* Solution1: Math Problem, 经典算法? Time. O(n) + O(n) + reverse O(n) -> O(n)
	* 对于序列(2,3,6,5,4,1)
	* 1. right to left, 找到第一个violate 升序的字符 -->PartitionNumber 3
	* 2. 判断这是不是最后一个数，如果是，说明原序列，比如3,2,1 全部降序，直接return reverse
	* 如果不是：
	* 3. right to left, 找到第一个比 3 大的数字.ChangeNumber --> 4 (这块编程时候可以从前往后找<3的，然后--)
	* 4. swap 3, 4 --> 2,4,6,5,3,1
	* 5. reverse (6,5,3,1) --> 2,4,1,3,5,6
	*
	* 很多材料都写了这个算法，但是没说明为什么。 其实这就是我们根据我们算Permutation 所有解得过程，我自己开始的想法是求出来所有的Permutation.
	* 因为都是升序，arrayList next一定是(如果是最后一个解，则return first). 理解了这个自然就明白这个算法，所以是反过来找，
	* 先反过来找violate increasing的number, 因为这个violate的那个number需要++，6,5,4,1已经没有升序可能了
	* 所以从右找到了第一个大于他的书，next step，PatitionNumber就会变成ChangeNumber. 然后后面部分重新摆列，所以是逆序。
	*
	* Reference:
	* http://fisherlei.blogspot.com/2012/12/leetcode-next-permutation.html
	* http://codeganker.blogspot.com/2014/03/next-permutation-leetcode.html
	* @author jeffwan
	* @date Apr 15, 2014
	*/
	public class NextPermutation {
	public void nextPermutation(int[] num) {
	if (num == null || num.length == 0) {
	return;
	}
	int i = num.length - 2;
	while(i >= 0 && num[i] >= num[i+1]) {
	i--;
	}
	if (i >= 0) {
	int j = i + 1;
	while (j < num.length && num[j] > num[i]) {
	j++;
	}
	j--;
	// swap i PatitionNumber and j SwapNumber
	int temp = num[i];
	num[i] = num[j];
	num[j] = temp;
	}
	reverse(num, i+1);
	}
	private void reverse(int[] num, int start) {
	int end = num.length - 1;
	while (start < end) {
	int temp = num[start];
	num[start] = num[end];
	num[end] = temp;
	start++;
	end--;
	}
	}
	// Solution 2: Find out all permutations(sorted), and then we could get next. (Works but Time Limit Exceedced on LC)
	public void nextPermutation2(int[] num) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	ArrayList<Integer> list = new ArrayList<Integer>();
	// create a copy of original num[], sorted and use if for permutation.
	int[] sortedNum = new int[num.length];
	System.arraycopy(num, 0, sortedNum, 0, num.length);
	Arrays.sort(sortedNum);
	boolean[] visited = new boolean[num.length];
	helper(result, list, visited, sortedNum);
	// Wrap num[] to ArrayList for comparation
	ArrayList<Integer> origin = new ArrayList<Integer>(num.length);
	for (int i = 0; i < num.length; i++) {
	origin.add(num[i]);
	}
	// find the index of current num[]
	int i;
	for (i = 0; i < result.size(); i++) {
	if (result.get(i).equals(origin)) {
	break;
	}
	}
	// Give the next permutation value to num[]
	if (i == result.size() - 1) {
	for (int j = 0; j < result.get(0).size(); j++) {
	num[j] = result.get(0).get(j);
	}
	} else {
	for (int j = 0; j < result.get(i + 1).size(); j++) {
	num[j] = result.get(i + 1).get(j);
	}
	}
	}
	private void helper(ArrayList<ArrayList<Integer>> result,
	ArrayList<Integer> list, boolean[] visited, int[] num) {
	if (list.size() == num.length) {
	result.add(new ArrayList<Integer>(list));
	return;
	}
	for (int i = 0 ;i < num.length; i++) {
	if (visited[i] == true || (i != 0 && num[i] == num[i - 1] && visited[i - 1] == false)) {
	continue;
	}
	list.add(num[i]);
	visited[i] = true;
	helper(result, list, visited, num);
	visited[i] = false;
	list.remove(list.size() - 1);
	}
	}
	}

view raw NextPermutation.java hosted with ❤ by GitHub