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?

  1. First use 16-1 to get 15 — @note:@memorize: “-1” is key to understand, k-th permutation meaning k-1, (i.e. code line below k = k - 1; // k 变为 k - 1)
    • @note@note: eg: first permutation, k=1, after divided by 4!, 3!, 2!, 1!, should be 0,0,0,0,
    • but 1/1! will gerate 1, which is wrong!
    • so should be 0/1! = 0
  2. Divide 4 by 15! Get 0 remaining 15

  3. Divide 3 with 15! Get 2 remaining 3

  4. Divide 2 with 3! Get 1 remaining 1

  5. 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();
        }
    }
    

All Problems

All Solutions