Find the kth 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 k^th permutation sequence.

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

The idea is to firstly find the number at the first position. At position n, the total number of permutations of remaining digits is (n-1)! Therefore k/(n-1)! can tell us which number should be placed at the first place. Then we iteratively find the next number after the first one. At this time, we again calculate the position of the number similarly, by reducing n to n-1. However, we should pick the position from the remaining digits. Thus we use an ArrayList to do so. As elements can be added to or removed from an arraylist conveniently, we can easily get the number at position pos.

Java: Permutation Sequence

01 public String getPermutation(int n, int k) {      
02   StringBuffer sb=new StringBuffer();      
03   ArrayList<Integer> ll=new ArrayList<Integer>();
04   for(int i=0;i<n;i++)
05   {
06     ll.add(i+1);
07   }
08   doPermute(sb,n,k-1,ll);      
09   return sb.toString();
10 }
11 
12 public int factorial(int n)
13 {
14   if(n<=1)
15     return 1;
16   int fact=n;
17   while(--n>=1)
18   {
19     fact=fact*n;
20   }
21   return fact;
22 }
23 public void doPermute(StringBuffer sb, int n, int k, ArrayList<Integer> ll)
24 {
25   int numGroup;
26   int pos;
27   int val;
28   while(n>=1)
29   {
30     numGroup=factorial(n-1);
31     pos=k/numGroup;
32     val=ll.get(pos);
33     ll.remove(pos);
34     sb.append(val);                    
35     k=k%numGroup;
36     n--;      
37   }
38 }