给定一个按字典顺序排列的元素列表(即['a'，'b'，'c'，'d'])，找到第n个排列-平均求解时间? [英] Given a list of elements in lexicographical order (i.e. ['a', 'b', 'c', 'd']), find the nth permutation - Average time to solve?

问题描述

我偶然发现了这个面试问题:

I stumbled across this interview question:

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

Given a list of elements in lexicographical order (i.e. ['a', 'b', 'c', 'd']), find the nth permutation

我自己尝试过，大约花了30分钟才能解决. (我最终在Python中找到了大约8-9行的解决方案).只是好奇-解决这类问题需要多长时间?我花了太长时间吗?

I tried it myself, and it took me about ~30 minutes to solve. (I ended up with a ~8-9 line solution in Python). Just curious -- how long "should" it take to solve this type of problem? Am I taking too long?

推荐答案

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)

这篇关于给定一个按字典顺序排列的元素列表(即['a'，'b'，'c'，'d'])，找到第n个排列-平均求解时间?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！