Permutation Sequence

Description

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 for n = 3:

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

Given n and k, return the k^th permutation sequence.

Note:

• Given n will be between 1 and 9 inclusive.
• Given k will be between 1 and n! inclusive.

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Solution(javascript)

const getPermutation = (n, k) => {
  const factorial = (number) => {
    let i = 1
    let result = 1
    while (i <= number) {
      result *= i
      i += 1
    }
    return result
  }
  const numbers = new Array(n).fill(0).map((v, index) => index + 1)

  const aux = (list = [], currentK, acc) => {
    if (list.length === 1) {
      return acc + list[0]
    }
    const length = factorial(list.length - 1)
    const nth = Math.ceil(currentK / length)
    return aux(list.filter(v => v !== list[nth - 1]), currentK - length * (nth - 1 < 0 ? 0 : nth - 1), `${acc}${list[nth - 1]}`)
  }
  return aux(numbers, k, '')
}