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