https://leetcode.com/problems/permutation-sequence/description/
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 for n = 3:
1."123"
2."132"
3."213"
4."231"
5."312"
6."321"
Given n and k, return the kth permutation sequence.
Note:
- Given n will be between 1 and 9 inclusive.
- Given k will be between 1 and n! inclusive.
他們可以組成有N!種排列，請問第k種是甚麼？
[Solution]
Let's assume we have N position for these N numbers. Then we will have N! permutations.
And they are indexed from 1~N!. We have a question :
What's the relation between the "index" and "the content of the permutation"?
The content contributes index in two ways :
1. The position
2. The rank of that number.
Let's go through it one by one.
1.The position
Different position have different amount of contribution to index.
For example:
The 1st(left most) position contribute (N-1)! to the index.
The 2nd position contribute (N-2)! to the index.
...
The k-th position contribute (N-k)! to the index.
2. The rank of that number.
Each number have a rank in the remaining numbers.
For example:
In sorted array [3,5,6,8,..x,..N], they are ranked by their place in the remaining sorted array.
'3' is the first number, it's rank is 0.
'5' is the second number, it's rank is 1.
'6' is the third number, it's rank is 2.
'8' is the fourth number, it's rank is 3.
Assume 'x' is the k-th number, it's rank is k-1.
And please note that rank is related to "remaining" sorted array. Which means it will change after you delete someone in the original array.
For example:
If we remove '5' from [3,5,6,8,..x,..N], then 6's rank will become 1.
Because it's become the second number in the remaining sorted array.
So does '8', 'k', .., 'N'.
If we remove '5' from [3,
Because it's become the second number in the remaining sorted array.
So does '8', 'k', .., 'N'.
For example:
We have a sorted array [3,5,6,8,..x,..N],
For position 1:
I choose '5' (which is rank 1).
It will contribute rank*(N-1)! which is 1*(N-1)!.
It means if a permutation start from '5...', it's index must bigger than 1*(N-1)!.
For position 2:
After '5' being chosen, the remaining number is [3,6,8,..x,..N].
Then we choose '6' (which is rank 1 of the remaining number)
It will contribute rank*(N-2)! which is 1*(N-2)!.
It means if a permutation start from '56..', it's index must bigger than 1*(N-1)! + 1*(N-2)!.
For position 3:
After '5'&'6' being chosen, the remaining number is [3,8,..x,..N].
...and so on..
If you choose a number and put it in certain position,
it contribute (chosen number's rank ) * (N-position)! to the index.
---
反過來問, 如果給你一串數字 (5,9,1), 請問這是編號幾的permutation?
(編號從0開始)
算法:
1.Ranking the remaining R numbers from 0 to R-1.
e.g. remaining number = (1,5,9), corresponding rank = (0,1,2)
2.Choose one from them, it will contribute (chosen number's rank) * (R-1)!
e.g. choose 5 from remaining numbers (1,5,9), it will contribute 1(rank) * (3-1)!
3.After 1&2, the remaining number become(1,9). It is a smaller question can be solved by repeat step 1&2
4.Added all contribution of step2, you will get the answer.
so the whole sequence is :
1. remaining=(1,5,9), rank=(0,1,2)
2. pick 5 : contribution = 1 * (3-1)! = 2
1. remaining=(1,9), rank=(0,1)
2. pick 9 : contribution = 1 * (2-1)! = 1
1. remaining=(1), rank=(0)
2. pick 1 : contribution = 0 * (1-1)! = 0
4. answer = 2+1+0 = 3
159 #0
195 #1
519 #2
591 #3 <---correct
915 #4
951 #5
---
And we can use this conclusion the other way around.
Since the index is contributed by those numbers and positions, how about I eliminate them one by one from the index.
When we get an index K :
K / (N-1)! --> this is the rank of the number in position 1. Then we eliminate it by K=K/(N-1)!
K / (N-2)! --> this is the rank of the number in postiton 2. Then we eliminate it by K=K/(N-2)!
...and so on..
Then we will know what are those numbers in each position.
Since the index is contributed by those numbers and positions, how about I eliminate them one by one from the index.
When we get an index K :
K / (N-1)! --> this is the rank of the number in position 1. Then we eliminate it by K=K/(N-1)!
K / (N-2)! --> this is the rank of the number in postiton 2. Then we eliminate it by K=K/(N-2)!
...and so on..
Then we will know what are those numbers in each position.
class Solution {
public:
string getPermutation(int n, int k) {
k=k-1;//my index start from 0, but the input start from 1
string res;
string s;//generate number '1'~'n'
for(int i=1;i<=n;i++)
s.push_back(i+'0');
//prepare an array for querying factorial
int f[n+1];
f[0]=1;
for(int i=1;i<n+1;i++)
f[i]=f[i-1]*i;
// for each position, find the corresponding number
for(int i=0;i<n;i++){
int position = i+1;
int rank = k / f[n-position];
res.push_back(s[rank]);
s.erase(rank,1);
k = k%f[n-position];
}
return res;
}
};
