Kth Permutation

Problem

Return the k-th permutation (1-indexed) of the numbers 1 through n in lexicographic order, as a string.

The first position is chosen by dividing k - 1 by (n - 1) factorial, then the process repeats on the remaining numbers with the remainder. Assume 1 <= k <= n factorial.

Hint

Each remaining position blocks together (size - 1) factorial permutations.

Test cases

case 1

in: [3,3]

expected: "213"

case 2

in: [4,9]

expected: "2314"

case 3

in: [3,1]

expected: "123"

case 4

in: [1,1]

expected: "1"

case 5

in: [3,6]

expected: "321"

Starter codePython

def kth_permutation(n, k):
    # Your code here
    pass

5 test cases · run your code against them in the editor