Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/60.html
60. 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 kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
@tag-backtracking
@tag-math
Algorithm
Math
Assuming there are n
elements, the K-th permutation result string is
a1, a2, a3, ..... ..., an
So which number is a1?
So here, we remove a1, then the remaining permutation is
a2, a3, .... .... an
, a total of n-1 elements. There are n-1 elements in total (n-1)!
group arrangement, then you can know
Set variable K1 = K
,
a1 = K1 / (n-1)!
Similarly, the value of a2 can be derived as
a2 = K2 / (n-2)!
K2 = K1 % (n-1)!
.......
a(n-1) = K(n-1) / 1!
K(n-1) = K(n-2) / 2!
an = K(n-1)
Cantor Expand
How to find the 16th (lexicographically) {1,2,3,4,5} permutation?
- First use
16-1
to get15
— @note:@memorize: “-1” is key to understand,k-th
permutation meaning k-1, (i.e. code line belowk = k - 1; // k 变为 k - 1
)@note@note
: eg: first permutation, k=1, after divided by4!, 3!, 2!, 1!
, should be0,0,0,0
,- but
1/1!
will gerate 1, which is wrong! - so should be
0/1! = 0
-
Divide 4 by 15! Get 0 remaining 15
-
Divide 3 with 15! Get 2 remaining 3
-
Divide 2 with 3! Get 1 remaining 1
- Divide 1 by 1! Get 1 more than 0
There are 0 numbers smaller than it is 1, so the first digit is 1.
There are 2 numbers that are smaller than it is 3, but 1 has appeared before, so it is 4.
There is 1 number smaller than it is 2, but 1 has appeared before, so it is 3.
There is 1 number smaller than it is 2, but 1, 3, and 4 have all appeared, so it is 5.
The last number can only be 2
So the arrangement is 1 4 3 5 2
Code
-
import java.util.ArrayList; import java.util.List; public class Permutation_Sequence { public static void main(String[] args) { Permutation_Sequence out = new Permutation_Sequence(); Solution s = out.new Solution(); System.out.println(s.getPermutation(4, 17)); // 3412 } // time: O(N) // space: O(N) public class Solution { public String getPermutation(int n, int k) { List<Integer> nums = new ArrayList<Integer>(); List<Integer> factorial = new ArrayList<Integer>(); // total `n` elements factorial.add(1); for (int i = 1; i <= n; i++) { nums.add(i); // size=n+1, will be [1,1,2,6,24] // so that, factorial(k) is `k!` factorial.add(factorial.get(i - 1) * i); } StringBuilder result = new StringBuilder(); k = k - 1; // k 变为 k - 1 for (int i = n; i > 0; i--) { int digit = k / factorial.get(i - 1); result.append(nums.get(digit)); k %= factorial.get(i - 1); nums.remove(digit); // remove by object } return result.toString(); } } } ############ class Solution { public String getPermutation(int n, int k) { StringBuilder ans = new StringBuilder(); boolean[] vis = new boolean[n + 1]; for (int i = 0; i < n; ++i) { int fact = 1; for (int j = 1; j < n - i; ++j) { fact *= j; } for (int j = 1; j <= n; ++j) { if (!vis[j]) { if (k > fact) { k -= fact; } else { ans.append(j); vis[j] = true; break; } } } } return ans.toString(); } }
-
// OJ: https://leetcode.com/problems/permutation-sequence/ // Time: O(NK) // Space: O(1) class Solution { public: string getPermutation(int n, int k) { string ans; for (int i = 0; i < n; ++i) ans += ('1' + i); while (--k) next_permutation(begin(ans), end(ans)); return ans; } };
-
class Solution: def getPermutation(self, n: int, k: int) -> str: nums = list(range(1, n + 1)) factorial = [1] * (n + 1) for i in range(1, n + 1): factorial[i] = factorial[i - 1] * i result = [] k -= 1 for i in range(n, 0, -1): digit = k // factorial[i - 1] result.append(str(nums[digit])) k %= factorial[i - 1] nums.pop(digit) return ''.join(result) ########## class Solution: def getPermutation(self, n: int, k: int) -> str: ans = [] vis = [False] * (n + 1) for i in range(n): fact = 1 for j in range(1, n - i): fact *= j for j in range(1, n + 1): if not vis[j]: if k > fact: k -= fact else: ans.append(str(j)) vis[j] = True break return ''.join(ans) ############ class Solution(object): def getPermutation(self, n, k): """ :type n: int :type k: int :rtype: str """ visited = [0 for i in range(n)] fact = [math.factorial(n - i - 1) for i in range(n)] ans = "" k -= 1 for i in range(n): t = k / fact[i] for j in range(n): if not visited[j]: if t == 0: break t -= 1 ans += str(j + 1) k %= fact[i] visited[j] = 1 return ans
-
func getPermutation(n int, k int) string { ans := make([]byte, n) vis := make([]bool, n+1) for i := 0; i < n; i++ { fact := 1 for j := 1; j < n-i; j++ { fact *= j } for j := 1; j <= n; j++ { if !vis[j] { if k > fact { k -= fact } else { ans[i] = byte('0' + j) vis[j] = true break } } } } return string(ans) }
-
public class Solution { public string GetPermutation(int n, int k) { var ans = new StringBuilder(); int vis = 0; for (int i = 0; i < n; ++i) { int fact = 1; for (int j = 1; j < n - i; ++j) { fact *= j; } for (int j = 1; j <= n; ++j) { if (((vis >> j) & 1) == 0) { if (k > fact) { k -= fact; } else { ans.Append(j); vis |= 1 << j; break; } } } } return ans.ToString(); } }