Permutation Sequence 解答

Question

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.

Solution -- Math

We can conclude a pattern by obeservation.

[x₁, x₂, x₃, .., x_n]

If we fix x₁, then number of permutations is (n - 1)!

If we fix x₁and x₂, then number of permutations is (n - 2)!

Following this thinking way, we can solve this problem by finding x_i iteratively.

We also need a visited array here to note which element has been used.

 1 public class Solution {
 2     public String getPermutation(int n, int k) {
 3         StringBuilder sb = new StringBuilder(n);
 4         if (n < 1 || n > 9)
 5             return sb.toString();
 6         int factorial = 1;
 7         for (int i = 1; i <= n; i++) {
 8             factorial *= i;
 9         }
10         if (k > factorial || k < 1)
11             return sb.toString();
12         boolean[] visited = new boolean[n];
13 
14         int num = n;
15         int start = 1;
16         while (num > 0) {
17             factorial /= num;
18             start += (k / factorial);
19             if (k % factorial == 0)
20                 start -= 1;
21             int index = 0;
22             for (int i = 1; i <= n; i++) {
23                 // Find the right index
24                 if (!visited[i - 1])
25                     index++;
26                 if (index == start) {
27                     sb.append(i);
28                     visited[i - 1] = true;
29                     break;
30                 }
31             }
32             k = k - (start - 1) * factorial;
33             start = 1;
34             num--;
35         }        
36         return sb.toString();
37     }
38 }