Next Permutation, Permutation, Permutations II, Permutation Sequence

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

Solution

Find the following pattern:

1. From right to left, find the first digit (PartitionNumber) which violate the increase trend.

2. From right to left, find the first digit which larger than PartitionNumber, call it ChangeNumber.

3. Swap the PartitionNumber and ChangeNumber.

4. Reverse all the digit on the right of partition index.

public static void nextPermutation(int[] nums) {
    	int i=nums.length-1;
    	while(i>0 && nums[i-1]>=nums[i]){
    		i--;
    	}
    	i--;
  
    	if(i<0) {
    		reverse(nums,0);
    		return ;
    	}
    	int j=nums.length-1;
    	while(j>i && nums[j]<=nums[i]){
    		j--;
    	}
      	 
    	//swap i,j
    	int tmp=nums[i];
    	nums[i]=nums[j];
    	nums[j]=tmp;

    	//reverse the partition after i
    	reverse(nums, i+1);

    	return;
    }
    
   private static void reverse(int[] nums, int i){
	   int l=i, r=nums.length-1;
	   while(l<r){
			int tmp=nums[l];
			nums[l]=nums[r];
			nums[r]=tmp;
			l++;
			r--;
	   }
	   return;
   }

---

Permutation

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].

DFS Solution

• Each digit has n possible values
• If containing the same values as previous ones, continue
• When reached end level, remove last element from list

public static List<List<Integer>> permute(int[] nums) {
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	List<Integer> tmp = new ArrayList<Integer>();
    	dfs(result,tmp,nums);
    	return result;
    }
    
    private static void dfs(List<List<Integer>> result,List<Integer> tmp, int[] nums){
    	if(tmp.size() == nums.length) {
    		result.add(new ArrayList<Integer>(tmp));
    		return;}
    	 
    	for(int i=0;i<nums.length;i++){
    		if(tmp.contains(nums[i])) continue;
			 tmp.add(nums[i]);
			 dfs(result, tmp, nums);
			 tmp.remove(tmp.size()-1);
    		}
    	return;
    }

---

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].

Solution

• Similar to Permutations, we only need to make sure not using the same element twice in the same way
• Use Visited[] to keep track of currently used element
• After sorted, if previous element is not visited and the same with current, then this will be duplicate permutation

public static List<List<Integer>> permuteUnique(int[] num) {
      List<List<Integer>> result = new ArrayList<List<Integer>>();
      if(num == null || num.length == 0)
          return result;
      List<Integer> list = new ArrayList<Integer>();
      int[] visited = new int[num.length];
      
      Arrays.sort(num);
      helper(result, list, visited, num);
      return result;
  }
  
  public static void helper(List<List<Integer>> result, List<Integer> list, int[] 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] == 1 || (i != 0 && num[i] == num[i - 1] && visited[i - 1] == 0)){
              continue;
          }
          visited[i] = 1;
          list.add(num[i]);
          helper(result, list, visited, num);
          list.remove(list.size() - 1);
          visited[i] = 0;
      }
  }

---

Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.

DFS Solution

• Find kth permutation, LTE…

public static String getPermutation(int n, int k) {
        int[] count={0};
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        tmp = dfs(tmp, n, k, count);
        StringBuilder re= new StringBuilder();
        for(int i : tmp){
            re.append(i);
        }
        return re.toString();
    }
    private static ArrayList<Integer> dfs(ArrayList<Integer> tmp, int n , int k, int[] count){
    
        if(tmp.size() == n){
            count[0]++;
            if(count[0]==k) return tmp;
            else return null;
        }
        for(int i=1; i<=n; i++){
            if(tmp.contains(i)) continue;
            tmp.add(i);
            ArrayList<Integer> res = dfs(tmp, n, k, count);
            if(res!= null) return res;
            tmp.remove(tmp.size()-1);
        }
        return null;
    }

Math Solution

Find the following pattern:

• To find kth sequence, (k-1)/(n-1)! will be the index of the number to be added
• We have elimated (k-1)/(n-1)! (n-1)! tuples, so keep finding k-(k-1)/(n-1)! (n-1)! === k%(n-1)! in the sub problems

public static String getPermutation(int n, int k){
       StringBuilder sb = new StringBuilder();
       k=k-1;
       int factorial=1;
       for(int i=1;i<n;i++){
           factorial*=i;
       }
       ArrayList<Integer> nums = new ArrayList<Integer>();
       for(int i=1; i<=n; i++) {
           nums.add(i);
       }
       while(n>1){
           int index = k/factorial;
           sb.append(nums.get(index));
           nums.remove(index);
           k = k%factorial;
           factorial = factorial/(n-1);
            
           n--;
       }
       sb.append(nums.get(0));
       return sb.toString();
   }