Permutation Sequence

Q:
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 k^th permutation sequence.
Note: Given n will be between 1 and 9 inclusive.

A:

public class PermutationSequence {
    public String getPermutation(int n, int k) {
        ArrayList<Integer> origList = new ArrayList<Integer>();
        //add 1 to n into the list, and delete them one by one
        ArrayList<Integer> resultList = new ArrayList<Integer>();
        //add 1 to n into the origList, and delete them one by one
        for(int i =1;i<=n;i++){
            origList.add(i);
        }
        int[] numPerm = new int[n+1];
        numPerm[0] = 1;
        for(int i =1;i<=n;i++){
            numPerm[i] = numPerm[i-1]*i;
        }
        //  for each iteration ,find the number that should be 
        for(int i =1;i<=n;i++){ /// find the i_th position
            int numCounted = 1;
            int numLeftPermu = numPerm[n-i];
            while(numCounted*numLeftPermu < k ){
                numCounted ++;
            }
            numCounted--;
            k = k - numCounted*numLeftPermu;
            int extractedValue = origList.remove(numCounted);
            resultList.add(extractedValue);
        }
        StringBuffer buf = new StringBuffer();
        for(int i =0;i<resultList.size();i++){
            buf.append(resultList.get(i )+"");
        }
        return buf.toString();
    }

}

------------第二遍，------------感觉还没有第一遍思路清晰---------为什么呢？？？ ----------

public class Solution {
        public String getPermutation(int n, int k) {
        // use list ,so that we can easily delete on item
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++)
            list.add(i);

        int result[] = new int[n];
        // calculate how many permutation for this count = index i
        int count[] = new int[n+1];
        count[0] = 1;
        for (int i = 1; i <= n; i++)
            count[i] =  i  * count[i-1]; // couting backward
        
        for (int i = 0; i < n; i++) { // for n position of
            for (int j = 0; j < list.size(); j++) {
                if ((j + 1) * count[ list.size() -1] >= k) {
                    // we should start from list.get(j)
                    result[i] = list.remove(j);
                    k -= j*count[list.size() ];
                    break;
                }
            }
        }

        String tmp = Arrays.toString(result).replace(", ","");;
        return tmp.substring(1,tmp.length()-1);
    }

}

Mistakes:
1: 最后的 buf.append(resultList.get(i )+"");  开始的时候，由于光考虑 i 转成string的情况去了，因此，直接写的是 buf.append( i +"");
可惜了啊， 否则就是直接pass过了， O(∩_∩)O哈哈~


2： 第二遍的时候，
    if ((j + 1) * count[ list.size() -1] >= k) {     这里，  要有等号的，仔细想想，为什么


-----------------------------------------3 rd Pass -----------------------------------------
TMD 就是脑子不清醒，非想要一个循环。 哎，至于吗？ 浪费了好几个小时。

结果明白了一点儿。  要计算k_th的permu，由于我们是用了一个数组， nPerm【】 来计算少了一个的数的时候，有多少个变化。 是在求 之前的变化。  因此，我们在计算
前面多少个重复的时候，应该用  k-1 来计算前面的变化数字。
哎，真为你的智商着急阿， Tiger

public class Solution {
    public String getPermutation(int n, int k) {
        ArrayList<Integer> al = new ArrayList<Integer>();
        StringBuffer buf = new StringBuffer();
        int[] nPermu = new int[n+1];// number of permutation before using index i
        nPermu[0] = 1;
        for(int i =1;i<=n;i++){
            nPermu[i] = i*nPermu[i-1];
            al.add(i);
        }
        // to get k-th, we need count k-1 before this one
        while(al.size()>0 ){// determine each digits from the highest 
            int nRepeat = (k-1) / nPermu[al.size()-1];
            k -= nRepeat * nPermu[al.size()-1];
            buf.append(al.remove(nRepeat));
        }
        return buf.toString();
    }
}

Learned: