给定按字典顺序排列的元素列表(即 ['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?
本文介绍了给定按字典顺序排列的元素列表(即 ['a', 'b', 'c', 'd']),找到第 n 个排列 - 平均求解时间?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我偶然发现了这个面试问题:
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屋!
查看全文