给定字典序元素列表，找第n个排列的平均解决时间是多少？

Question

我碰到一个面试问题：

给定一个按字典顺序排列的元素列表（比如 ['a', 'b', 'c', 'd']），找出第 n 个排列。

我自己尝试了一下，花了大约30分钟才解决这个问题。（最后我用Python写了大约8-9行代码）。我只是好奇——解决这种问题“应该”花多长时间呢？我是不是花太久了？

Answer 1

也许我漏掉了什么，我原以为我们可以很容易地通过 itertools 的 nth 这个功能 和 排列组合的功能 来找到它：

from itertools import permutations, islice
def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)
def main():
    data = ['a', 'b', 'c', 'd']
    n = 7  # 0 indexed
    print nth(permutations(data), n)
if __name__ == "__main__":
    main()

Answer 2

如果有人对找到“第 i 个”排列感兴趣，尤其是在查看“r 长度排列”时（这个“r”就是 itertools.permutations 里的参数），可以参考以下内容：

from math import factorial

def ith_permutation(i, seq, r=None):
    li = list(seq)
    length = len(li)

    if r is None:
        r = length
    res = []
    current_factorial = factorial(length) // factorial(length - r)

    if current_factorial <= i:
        raise ValueError('out of range')

    for x in range(length, length-r, -1):
        current_factorial //= x
        div, mod = divmod(i, current_factorial)
        i = mod
        res.append(li[div])
        del(li[div])

    return res

举个例子：

>>> ith_permutationutation(10, [0, 1, 2, 3, 4], 2)
[2, 3]

>>> # correctness check:
>>> from itertools import permutations
>>> list(permutations([0, 1, 2, 3, 4], 2))[10]
(2, 3)

这里还包括了一个更完整的测试：

s = range(8)
for n in range(len(s)):
    for idx, item in enumerate(permutations(s, n)):
        assert list(item) == ith_permutation(idx, s, n)

这里用到了 Karoly Horvath 答案中的一些部分。

Answer 3

包括测试在内，总共需要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)