The title

Give the set [1,2,3… n] in which all elements have n! Kind of arrangement.

All permutations are listed in order of size and marked one by one. When n = 3, all permutations are as follows:

  1. “123”
  2. “132”
  3. “213”
  4. “231”
  5. “312”
  6. “321”

Given n and k, return the KTH permutation.

LeetCode portal 60. Permutation sequence

solution

So what I’m going to do is I’m going to do the dumbest way I can, which is I’m going to do all the permutations from smallest to largest, and then I’m going to take the KTH one. The result timed out, later used mathematical method to fix, first come to see my violence law 😂.

Violence law

var getPermutation = function (n, k) {
    // Create an array permutationList to record the elements that have already been used
    const originList = [], permutationList = []
    let i = 0
    while (i < n) {
        originList.push(++i)
    }
    for (let i = 0; i < n; i++) {
        const newAns = [originList[i]]
        getsubPermutation(newAns, originList, permutationList, n)
    }
    return permutationList[k - 1]};// Arrange the combinators one by one
function getsubPermutation(newAns, nums, ans, length) {
    if (newAns.length === length) {
        ans.push(newAns.join(' '))
        return
    }
    for (let i = 0; i < length; i++) {
        // Iterate over all elements and skip if the current element is in use
        if (newAns.includes(nums[i])) {
            continue
        }
        const _newAns = [...newAns, nums[i]]
        getsubPermutation(_newAns, nums, ans, length)
    }
}
Copy the code

Obviously that’s not going to work, because he’s going to run out of time at n equals 9, although he’s going to work out the answer, so he’s going to have to do it the right way, and that’s the math.

Mathematics method

For n distinct elements (e.g., the numbers 1, 2… n), the total number of permutations they can form is n! .

We can determine a1 by the magnitude of k.

Here’s how it works

There are (n−1) permutations of 1 as A1! A;

There are n minus 1 factorial permutations of 2 as a1. A;

There’s n minus 1 factorial of 3 a1. A;

.

There are n−1 permutations of n as A1! A.

If k <= (n−1)! I can determine that the first element of the permutation is 1

If (n – 1)! < k < = 2 (n – 1)! I can determine that the first element in the permutation is 2

If (n – 1) (n – 1)! < k < = n (n – 1)! I can determine that the first element of the permutation is n

So the first element of the KTH permutation is math.fool (k-1/(n-1)!). + 1

In this way, we have transformed the original problem into a subproblem of exactly the same size but reduced by one:

Find the set [1,2… n] to exclude the KTH ‘smallest permutation of the n−1 permutation already composed of element a1.

And then the problem is narrowed down to a permutation of the individual elements and you’ve got the solution at this point

var getPermutation = function (n, k) {
    // Initialize result, set of elements to be used, set element container, number of elements in the next subarrangement n
    let permutation = ' ', permutationElementSet = new Set(), allElement = [], nextN = n
    const i = k - 1
    
    // Initialize all elements
    for (let j = 1; j <= n; j++) {
        allElement.push(j)
    }
    
    / / calculate a1
    const a1 = Math.floor(i / getFactorial(n - 1)) + 1
    permutation += a1

    permutationElementSet.add(a1)
    // Exclude elements that have already been used
    allElement = allElement.filter(element= > {
        return! permutationElementSet.has(element) })// Not complete until all subpermutations are computed
    while(permutation.length ! == n) {// compute the first item of the subpermutation a1
        permutation += getA1(nextN, i, allElement, permutationElementSet)
        // Exclude elements that have already been used
        allElement = allElement.filter(element= > {
            return! permutationElementSet.has(element) }) nextN-- }return permutation

};
// Compute the first term of the subpermutation a1
function getA1(n, i, allElement, set) {
    // select * from k;
    const a1Index = Math.floor(i % getFactorial(n - 1))
    // Get the first item a1 ((n-1) set of elements each containing (n-2)! Subcombination)
    const a1 = allElement[Math.floor(a1Index / getFactorial(n - 2))]
    set.add(a1)
    return a1
}

/ / factorial
function getFactorial(n) {
    let res = 1
    while (n > 1) {
        res *= n
        n--
    }
    return res
}
Copy the code

Submit the test