Permutation Sequence 求第k个的排列序列 @LeetCode

思路：

1 求出所有的排序，直到k为止。至少Java会超时。

2 数学，找规律，不好想！ 参考http://fisherlei.blogspot.com/2013/04/leetcode-permutation-sequence-solution.html

假设有n个元素，第K个permutation是
a1, a2, a3, ..... ..., an
那么a1是哪一个数字呢？

那么这里，我们把a1去掉，那么剩下的permutation为
a2, a3, .... .... an, 共计n-1个元素。 n-1个元素共有(n-1)!组排列，那么这里就可以知道

设变量K1 = K
a1 = K1 / (n-1)! // 第一位的选择下标

同理，a2的值可以推导为

K2 = K1 % (n-1)!
a2 = K2 / (n-2)!

。。。。。

K(n-1) = K(n-2) /2!
a(n-1) = K(n-1) / 1!

an = K(n-1)

package Level5;

import java.util.Arrays;


/**
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):

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.
 *
 */
public class S60 {

	public static void main(String[] args) {
		System.out.println(getPermutation(3, 3));
	}

	static int maxDep;
	static StringBuilder ret;
	static boolean[] canUse;
	static int[] num;
	static int kth;
	static String save = "";
	
	// 数学方法
	public static String getPermutation(int n, int k) {
		int[] nums = new int[n+10];
		int permCount = 1;
		
		for(int i=0; i<n; i++){
			nums[i] = i+1;				// nums装有1,2,3,4,...,n
			permCount *= (i+1);		// 最后计算出permCount = n!
		}
		
		k--;		// 对k减一，因为现在index是从[0,n-1]而不是[1,n]
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n; i++){
			permCount = permCount / (n-i);
			int idx = k / permCount;	// 该位应该选择的下标
			sb.append(nums[idx]);
			// 重建nums，左移一位
			for(int j=idx; j<n-i; j++){
				nums[j] = nums[j+1];
			}
			k %= permCount;
		}
		return sb.toString();
	}
	
	// 递归求所有的排列，超时
	public static String getPermutation2(int n, int k) {
        kth = k;
		
		StringBuilder done = new StringBuilder();
		StringBuilder rest = new StringBuilder();
		for(int i=1; i<=n; i++){
			rest.append(i);
		}
		
		rec(done, rest);
		return save;
    }
	
	public static void rec(StringBuilder done, StringBuilder rest){
		if(rest.length() == 0){
			kth--;
			if(kth == 0){
				save = done.toString();
			}
			return;
		}
		
		for(int i=0; i<rest.length(); i++){
			char c = rest.charAt(i);
			rest.deleteCharAt(i);
			done.append(c);
			rec(done, rest);
			done.deleteCharAt(done.length()-1);
			rest.insert(i, c);
		}
	}
	
	
	
	
}