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.

public class Solution {     /**	 * This is a trick problem. We need to use how a permutation is generated.
	 * Let us consider, for example, the first digit of the permutation.
	 * Number 1 on the first digit until (n - 1)! + 1-th permutation. and (n - 1)! is the last	 * permutation starts with 1. For the same reason 2*(n-1)!  is the last permutation starts with	 * number 2 and so on.  So, on the first digit of k-th permutation can be determined by	 * ((--k) / (n - 1)!). Recursively, we can find the other digits of the permutation.
	 * 	 	 * @param n --int, the number of digits in the permutation.	 * @param k --int, the k-th permutation which is looking for.	 * @return String --the permutation.	 * @author Averill Zheng	 * @version 2014-06-14	 * @since JDK 1.7	 */	public String getPermutation(int n, int k) {		List
     
       num = new ArrayList
      
       ();		int count = 1;		//add the number in the ArrayList and calculate the factorial		for(int i = 0; i < n; ++i){			num.add((i + 1));			count *= (i + 1);		}				//decrease k by 1		--k;				//find each digit of the permutation.		StringBuffer stb = new StringBuffer();		for(int i = 0; i < n; ++i){			count /= (n - i);			//select an item from the ArrayList and add to the permutation. After that remove 			//the digit from the ArrayList since it has been added to the permutation.			int itemToBeAdded = num.remove(k / count);			stb.append(itemToBeAdded); 			k %= count;		}		return stb.toString();    }}