LeetCode - 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):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

If this is a follow-up question of "next permutation" (see previous post), the first thought will be calling nextPermutation k times. That's expensive: we have to compute all previous k-1permutations even though we never gonna use them!

Take a look at the entire sequence.
The first number will not change to next until all permutations of the rest of n-1 numbers have shown up. That said, given n = 4, k = 15 (= 2 * 3! + 1 * 2! + 1 * 1! + 0), the first number will be 3 (the 3-rd of [1,2,3,4]), the second number will be 2 (the 2-nd of [1,2,4]), and the last two numbers will be 1 and 4 (the 1-st permutation of [1,4]).

By doing these math, we only need O(n) time to get an index for the current spot (O(n) time to compute n!).
Notice that the calculated index is a relative index and thus we need to shift the numbers after we find out the one for the current spot (or erase the current one if we use separate strings for original and k-th permutation).

So, the total running time is O(n^2) since we may need to shift O(n) times. Also, it takes extra O(n) space for the factorials to reduce redundant calculations.

 

1. 找没用过的里面的第(k – 1) / (n – 1)!个数字，放第一位上。
2. k = (k – 1) % (n – 1)!，第一个数字确定了，剩下这些里面重新找第k个。
3. n每次-1，比如第一位确定后有(n-1)!种后面数字的排法，第二位也确定了后面的数字排法就又少了一位(n – 1 – 1)!

public String getPermutation(int n, int k) {
    List<Integer> numberList = new ArrayList<Integer>();
    int[] fact = new int[n+1];
    fact[0] = 1;
	for(int i=1; i<=n; i++) {
		numberList.add(i);
		fact[i] = fact[i-1]*i;
	} 
    // change K from (1,n) to (0, n-1) to accord to index  
    k--;  
    String result = "";  
    for(int i=n-1; i>=0; i--)  {    
         int choosed = k / fact[i];
         k -= choosed*fact[i];
         // restruct numberList since one number has been picked  
         result += numberList.remove(choosed); 
    }  
    return result;  
}

 

Reference:

http://n00tc0d3r.blogspot.com/2013/05/permutation-sequence.html

http://yucoding.blogspot.com/2013/04/leetcode-question-68-permutation.html

http://www.programcreek.com/2013/02/leetcode-permutation-sequence-java/

http://leetcodenotes.wordpress.com/2013/10/20/leetcode-permutation-sequence/