给出字典顺序中的元素列表(即['a','b','c','d']),找到第n个排列 - 平均解决时间？

Question

我偶然发现了这个采访问题:

给出字典顺序中的元素列表(即['a','b','c','d']),找到第n个排列

我自己试了一下,花了大约30分钟才解决.(我最终在Python中使用了一个~8-9行解决方案).只是好奇 - 解决这类问题需要多长时间？我花了太长时间吗？

Answer 1

9分钟,包括测试

import math

def nthperm(li, n):
    n -= 1
    s = len(li)
    res = []
    if math.factorial(s) <= n:
        return None
    for x in range(s-1,-1,-1):
        f = math.factorial(x)
        d = n / f
        n -= d * f
        res.append(li[d])
        del(li[d])
    return res

#now that's fast...
nthperm(range(40), 123456789012345678901234567890)