M
tags: Math, Backtracking
TODO: what about regular DFS/backtracking to compute the kth? dfs(rst, list, candiate list, k)
k是permutation的一个数位。而permutation是有规律的。
也就是说，可以根据k的大小来判断每一个数位的字符（从最大数位开始，因为默认factorio从最大数位开始变化）。
于是先求出n!， 然后 k/n!就可以推算出当下这一个数位的字符。然后分别把factorio 和 k减小。
另外, 用一个boolean[] visited来确保每个数字只出现一次。
这个方法比计算出每个permutation要efficient许多。
```
/*
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.
Hide Tags Backtracking Math
Hide Similar Problems (M) Next Permutation (M) Permutations
*/
/*
Correct solution is to reduce k, and manipulate the sequence
http://www.jiuzhang.com/solutions/permutation-sequence/
Thoughts:
k is the sum of possibilities.
Based on attempt1, attempt2, we understand that each digit leads a differnet sets of possibilities. The total is n!
For example,
factorio = # of a paticular set of possibilities, and remain = (k / factorio) means how any sets are there.
If remain == 0, that means factorio has more possibiities than k (factorio > k) so there is nothing changed on 1st
char position. For example, if given [1,2,3], then the string will end up as '1xx'.
With the above fact, we can find out each char by calculate k vs. factorio.
Note, each round, the factorio itself need to reduced.
*/
public class Solution {
public String getPermutation(int n, int k) {
if (n <= 0 || k <= 0) {
return "";
}
StringBuffer sb = new StringBuffer();
boolean[] visited = new boolean[n];
//Largest possible number of posibilities, n!
int factorio = 1;
for (int i = 1; i < n; i++) {
factorio *= i;
}
//Put k into 0-base
k = k - 1;
for (int i = 0; i < n; i++) {
int index = k / factorio;
k = k % factorio;
for (int j = 0; j < n; j++) {
if (!visited[j]) {
if (index == 0) {
visited[j] = true;
sb.append((char)('0' + j + 1));
break;
} else {
index--;
}
}
}
if (i < n - 1) {
factorio = factorio / (n - i - 1);
}
}
return sb.toString();
}
}
/*
Based on attempt1, we can actually find every index in front by calling getPermutation(n,k) recursivly
Still timeout
*/
public class Solution {
public String getPermutation(int n, int k) {
if (n <= 0 || k <= 0) {
return "";
}
ArrayList nums = new ArrayList();
for (int i = 1; i <= n; i++) {
nums.add(i);
}
int frontInd = 0;
for (; frontInd < nums.size(); frontInd++) {
//find max # of permutations that's less than k, and start permutation with that perticular n at index 0.
int factorio = 1;
for (int i = 1; i < n; i++) {
factorio = factorio * i;
}
int startInd = frontInd;
int numPermute = factorio;
while (numPermute < k) {
numPermute += factorio;
startInd++;
}
if (startInd != frontInd) {
int temp = nums.get(startInd);
nums.remove(startInd);
nums.add(frontInd, temp);
k = k - numPermute;
n--;
}
}
StringBuffer sb = new StringBuffer();
for (int num : nums) {
sb.append(num);
}
return sb.toString();
}
}
/*
Attempt1: timeout
based on k[1 ~ k], find the max x that has x! < k, where x = [1 ~ n]
then swap (x + 1) and 1, start permutation, and find the (k - x!)th
*/
public class Solution {
public String rst = "";
public int index = 0;
public String getPermutation(int n, int k) {
if (n <= 0 || k <= 0) {
return "";
}
int[] nums = new int[n];
for (int i = 0; i < nums.length; i++) {
nums[i] = i + 1;
}
//find max # of permutations that's less than k, and start permutation with that perticular n at index 0.
int factorio = 1;
for (int i = 1; i < n; i++) {
factorio = factorio * i;
}
int startInd = 0;
int numPermute = factorio;
while (numPermute + factorio < k) {
numPermute += factorio;
startInd++;
}
if (startInd != 0) {
int temp = nums[startInd];//findMax return value in [1 ~ n], and we need index
nums[startInd] = nums[0];
nums[0] = temp;
k = k - numPermute;
}
permute("", k, nums);// startInd + 1 is in [1 ~ n]
return rst;
}
public void permute(String s, int k, int[] nums) {
if (rst.length() != 0) {
return;
}
if (s.length() == nums.length) {
index++;
if (index == k) {
rst = s;
}
return;
}
for (int i = 0; i < nums.length; i++) {
if (!s.contains(nums[i] + "")) {
permute(s + nums[i], k, nums);
}
}
}
}
```