A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

$$012\ 021\ 102\ 120\ 201\ 210$$

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?



In [124]:

    
from math import factorial
def n_th(n, m):
    n -= 1
    a = [i for i in range(0,m)]
    r = ''
    for k in range(m - 1, 0, -1):
        p = factorial(k)
        v = int(n/p)
        n %=  p
        r += str(a[v])
        del a[v]
    return r + str(a[0])



In [125]:

    
n_th(5, 3)









    Out[125]:





'201'



In [127]:

    
n_th(1000000, 10)









    Out[127]:





'2783915460'



In [128]:

    
%timeit n_th(1000000, 10)









    



100000 loops, best of 3: 10.9 µs per loop



In [ ]: