This question is asked at Amazon, Facebook, and Google. There are permutation sequences for a set, exactly n! permutation sequences. Here are all the permutations sequences for n = 3:
123
132
213
231
312
321
and given n and k, which is [1, 2, 3, ..., n] we want to return the kth permutation sequence. Here are the constraints and examples:
Example 1:
Input: n = 3, k = 3
Output: "213"
Example 2:
Input: n = 4, k = 9
Output: "2314"
Example 3:
Input: n = 3, k = 1
Output: "123"
Constraints:
1 <= n <= 9
1 <= k <= n!
So to list out all the permutations for (1, 2, 3, 4), I get
1 + (permutations of 2, 3, 4)
2 + (permutations of 1, 3, 4)
3 + (permutations of 1, 2, 4)
4 + (permutations of 1, 2, 3),
so the number of permutations are n!. There are 24 permutations and there are 6 possible permutations in these. I then subtract 12 from k, which would be
k - (index from previous) * n - 1! which index from previous is basically k / (n - 1). So, if we want to get the 14th element, we will get index number 13.
13 / 6 = 2. At index 2, the array has a value 3, so the first number is a 3. Now there are 3 permutations of 1, 2, and 4:
1 + (permutations of 2,4)
1 + (permutations of 1,4)
4 + (permutations of 1,2)
and now we have 6 choices. Each permutations of these numbers have 2 possibilities giving a total of 6 possibilities. We are looking for the first number, and this would be 1. Now the index now is k / (n - 2)! now and 1 / (4 - 2)! = 1/2 = 0, so we get the permutation from index 0. So the second number is 1.
{2,4} the third number. k would be k - previous * (n - 2)! which is 1 - 0 * (4 - 2)! = 1. Now we want to do k / (n - 3)! which is 1 / 1! = 1, which means that the third index of the number is 4.
{2} Now k = 1 - 1 * (4 - 3)! = 0. Third number index is 0/0! which is 0/1 which now index 0 here is 2, and this is how you found the fourteenth number.
So what do we do? We get an array of factorial lookup, and a list of numbers to get the indices, and then basically divide by factorial, get the number divided by the factorial (get this index), remove the index of this number, and then subtract this index multiplied by the factorial, while looping through these numbers. .remove() is an O(n) operation which would make the entire algorithm O(n^2).
And here's the solution:
public class Solution {
public String getPermutation(int n, int k) {
//initialize the number list from 1-n
List<Integer> numbers = new ArrayList<>();
//make a factorial table and a builder to build the string that is to be returned.
int[] factorial = new int[n + 1];
StringBuilder sb = new StringBuilder();
//create an array of factorials that we can use to look up
int sum = 1;
factorial[0] = 1;
for(int i = 1; i <= n; i++){
sum *= i;
factorial[i] = sum;
}
//put the number "indexes" in the array
for(int i = 1; i <= n; i++){
numbers.add(i);
}
//start at the correct index
k = k - 1;
//final algorithm
for(int i = 1; i <= n; i++){
//get the index of what number inside the permutation map to access
int index = k/factorial[n - 1];
//append this number
sb.append(String.valueOf(numbers.get(index)));
//remove the number from index, to create new numbers.
numbers.remove(index);
//update the k value to what is remaining or the modulus for the remaining factorial.
k -= index * factorial[n - i];
}
return String.valueOf(sb);
}
}
Comments
Post a Comment