题目：

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.

思路：

除法和求余运算，对每一组数往下递推

package permutation;import java.util.ArrayList;import java.util.List;public class PermutationSequence {    public String getPermutation(int n, int k) {        List
     
       l = new ArrayList
      
       ();        for (int i = 1; i <= n; ++i)             l.add(i);        --k;        StringBuilder sb = new StringBuilder();        for (int i = n; i > 0; --i) {            int fib = fib(i - 1);            int index = k / fib;            k = k % fib;            sb.append((char)('0' + l.get(index)));            l.remove(index);        }        return sb.toString();    }        private int fib(int n) {        int res = 1;        for (int i = 1; i <= n; ++i)            res *= i;        return res;    }        public static void main(String[] args) {        // TODO Auto-generated method stub        PermutationSequence p = new PermutationSequence();        System.out.println(p.getPermutation(4, 5));    }}