Permutation Sequence
https://oj.leetcode.com/problems/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 k
permutation sequence.
Note: Given n will be between 1 and 9
inclusive.
解答：
1. 以某一数字开头的排列有(n-1)! 个。
例如： 123， 132， 以1开头的是 2！个
2. 所以第一位数字就可以用 （k-1） / (n-1)! 来确定
.这里K-1的原因是，序列号我们应从0开始计算，否则在边界时无法计算。
3. 第二位数字。假设前面取余后为m，则第二位数字是 第 m/(n-2)! 个未使用的数字。
4. 不断重复2，3，取余并且对(n-k)!进行除法，直至计算完毕
以下为主页君的代码，敬请指正：
解法1：
采用比较复杂的boolean来计算数字的索引（我们需要用一个boolean的数组来记录未使用的数字）：
package Algorithms.permutation; /*
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 PermutationSequence {
public static String getPermutation(int n, int k) {
if (n == ) {
return "";
} // 先计算出(n)!
int num = ;
for (int i = ; i <= n; i++) {
num *= i;
} boolean[] use = new boolean[n];
for (int i = ; i < n; i++) {
use[i] = false;
} // 因为index是从0开始计算
k--;
StringBuilder sb = new StringBuilder();
for (int i = ; i < n; i++) {
// 计算完第一个数字前，num要除以(n)
num = num / (n - i); int index = k / num;
k = k % num; for (int j = ; j < n; j++) {
if (!use[j]) {
if (index == ) {
// 记录下本次的结果.
sb.append((j + ) + "");
use[j] = true;
break;
} // 遇到未使用过的数字，记录index
index--;
}
}
} return sb.toString();
} public static void main(String[] args) {
System.out.println(getPermutation(, ));
} }
解法2：
优化后，使用链表来记录未使用的数字，每用掉一个，将它从链表中移除即可。
public String getPermutation1(int n, int k) {
// 1:17 -> 1:43
LinkedList<Character> digits = new LinkedList<Character>();
// bug 2: should only add n elements.
for (char i = ''; i <= '' + n; i++) {
digits.add(i);
}
k = k - ;
StringBuilder sb = new StringBuilder();
int sum = ;
// n!
for (int i = ; i <= n; i++) {
sum *= i;
}
int cur = n;
while (!digits.isEmpty()) {
sum /= cur;
cur--;
int digitIndex = k / sum;
k = k % sum;
//Line 25: error: cannot find symbol: method digits(int)
sb.append(digits.get(digitIndex));
// remove the used digit.
digits.remove(digitIndex);
}
return sb.toString();
}解法3：
在2解基础进一步优化，使用for 循环替代while 循环，更简洁：
public String getPermutation(int n, int k) {
// 1:17 -> 1:43
LinkedList<Character> digits = new LinkedList<Character>();
// bug 2: should only add n elements.
for (char i = ''; i <= '' + n; i++) {
digits.add(i);
}
// The index start from 0;
k--;
StringBuilder sb = new StringBuilder();
int sum = ;
// n!
for (int i = ; i <= n; i++) {
sum *= i;
}
for (int i = n; i >= ; i--) {
sum /= i;
int digitIndex = k / sum;
k = k % sum;
//Line 25: error: cannot find symbol: method digits(int)
sb.append(digits.get(digitIndex));
// remove the used digit.
digits.remove(digitIndex);
}
return sb.toString();
}