05 August 2008
给一个n，找到所有的排列，从小到大排列，找到第k大的排列
The basic idea is to decide which is the correct number starting from the highest digit. Use k divide the factorial of (n-1), the result represents the ith not used number. Then update k and the factorial to decide next digit.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public String getPermutation(int n, int k) {
LinkedList<Integer> notUsed = new LinkedList<Integer>();
int weight = 1;
for (int i = 1; i <= n; i++) {
notUsed.add(i);
if (i == n)
break;
weight = weight * i;
}
String res = "";
k = k - 1;
while (true) {
res = res + notUsed.remove(k / weight);
k = k % weight;
if (notUsed.isEmpty())
break;
weight = weight / notUsed.size();
}
return res;
}