finds k th lexicographic permutation in increasing order of 0 1 2 n1 in on2 time examples first permutation is always 0 1 2 n kthpermutation0 5 0 1 2 3 4 the order of permutation of 0 1 2 3 is 0 1 2 3 0 1 3 2 0 2 1 3 0 2 3 1 0 3 1 2 0 3 2 1 1 0 2 3 1 0 3 2 1 2 0 3 1 2 3 0 1 3 0 2 kthpermutation10 4 1 3 0 2 factorails from 1 to n1 find permutation finds k th lexicographic permutation in increasing order of 0 1 2 n 1 in o n 2 time examples first permutation is always 0 1 2 n kth_permutation 0 5 0 1 2 3 4 the order of permutation of 0 1 2 3 is 0 1 2 3 0 1 3 2 0 2 1 3 0 2 3 1 0 3 1 2 0 3 2 1 1 0 2 3 1 0 3 2 1 2 0 3 1 2 3 0 1 3 0 2 kth_permutation 10 4 1 3 0 2 factorails from 1 to n 1 find permutation
def kth_permutation(k, n):
    
    
    factorials = [1]
    for i in range(2, n):
        factorials.append(factorials[-1] * i)
    assert 0 <= k < factorials[-1] * n, "k out of bounds"

    permutation = []
    elements = list(range(n))

    
    while factorials:
        factorial = factorials.pop()
        number, k = divmod(k, factorial)
        permutation.append(elements[number])
        elements.remove(elements[number])
    permutation.append(elements[0])

    return permutation


if __name__ == "__main__":
    import doctest

    doctest.testmod()