Python中的Euler # 24词汇表排列

Question

排列是物体的有序排列。例如，3124是数字1、2、3和4的一种可能的排列。如果所有的排列都是按数字或字母顺序排列的，我们称之为字典顺序。0、1和2的词典排列如下：

012 021 102 120 201 210

数字0、1、2、3、4、5、6、7、8和9的第百万位词典排列是什么？

import itertools


def lexicographic(n, digits):
    """Assumes digits a string.
    returns the nth item of the lexicographic permutation of digits."""
    return list(itertools.permutations(digits))[n - 1]


if __name__ == '__main__':
    permutation = list(lexicographic(1000000, '0123456789'))
    print(''.join(permutation))

Answer 1

你正在建立一个巨大的排列列表，这样才能得到一个排列。这是不必要地使用时间(计算它之前的所有排列)和内存(将所有这些排列存储在一个列表中)。

如果有9个对象，则可以有9！= 3,628,800排列。所以用10位数，从0到9，第一个362,880个排列将是0#########，下一个362,880个排列将是1#########，到2#‘S，你将达到第百万个置换，274,240个排列。所以，1位数下降，9位。

对于8个对象，可以有8！= 40,320排列。再次，您可以确定您将跨越274,240‘在第7组排列的9个物体: 013456789 .所以你的第一百万个排列将是27########的形式。

对其余的数字重复:计算器工作正常。或者编写一个程序来解决这个问题，答案将在一秒内直接返回。

Answer 2

itertools.islice()

看起来不错，但是生成所有排列的列表可能需要大量的内存。使用itertools.islice()跳过您不想要的第一个999,999排列。islice的索引参数与range(start, stop, step)的索引参数类似。

def lexicographic(n, digits):
    """Assumes digits a string.
    returns the nth item of the lexicographic permutation of digits."""

    full_sequence = itertools.permutations(digits)
    starting_at_n = itertools.islice(full_sequence, n-1, n)
    return next(starting_at_n)

您可能需要调整n-1部件，具体取决于问题是从零还是从1开始。

这仍然迭代所有的排列，所以它不是很有效的大序列。使用一些数学，您可以确定置换而不迭代它们。