Permutation Sequence

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

Analysis:
One way to solve the problem (can only pass the small test) is to generate from the 1st permutation to the required one (similar to the problem Next permutation.). However, when n=9, the last permutation is the 362880th one, which is too time consuming.

A better way is to fully use the properties of permutation: the total number of permutation with length n is n!.
First, let‘s take a look at how permutation works:

Every leave node is a permutation. Take a look at the second level, each subtree (second lever node as the root), there are (n-1)! permutations in it.  Totally there are n nodes in 2nd level, thus the total number of permutations are n*(n-1)!=n!.

So, what we wanna do is to locate one permutation among the leave nodes. The simple method is to generate and search each leave node until we find the one. Now, what we can do here we want to skip some trees to reduce the complexity. e.g. in the above tree, if we know the required leave node is in the third sub tree (under CBA), we can skip the first two and search from the "CBA".

Say we have the required permutation is the kth one, first we can locate which subtree it belongs to in the 2nd level, by computing s = k / ((n-1)!). Then we get the sth subtree, and set k=k%((n-1)!) , now search the sub tree until we get the leave node. How to get the sth subtree root node? Just like the idea of how permutation works (the first figure): Just put the sth elment after fixed letter.  e.g. ABCD,  we want the 3rd subtree root node in 2nd level, just put C in the 1st place, which is CABD;   For ABCDE, we want the 3rd subtree root node in the 3rd level, it is ADBCE.

public class Solution {
    public String getPermutation(int n, int k) {
     int[] num = new int [n];
     
     // count = !n
     int count = 1;
     for(int i = 0; i < n; i++){
         num[i] = i+1;
          count *= (i+1);
        }
     // n是从1开始 所以kth个 的下标为 k-1    
     k--;
     StringBuilder sb = new StringBuilder();
     for(int i = 0; i<n; i++){
        //  第i层 有多少种排列组合，注意 count是数组的下标,数组下标从 0 开始
             count /= n-i;
              // 应该选第 i层的第几个，注意 selected 是数组的下标,数组下标从 0 开始
         int selected = k / count;
         // 剪掉 第i层前面的， 得到新k
         k = k % count;
         
         sb.append(num[selected]);
         
         //restruct nums since one num has been picked  
         for(int j = selected+1; j<n; j++){
             num[j-1] = num[j];
         }
     }
     
     return sb.toString();
    }
    
    
}

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

http://www.cnblogs.com/feiling/p/3251230.html

[Leetcode]-- Permutation Sequence