Python列表和派生

Question

对于Project Euler问题24，我有以下(正确的)解决方案。我对Python比较陌生，在Python的几个要点上遇到了困难。

首先，代码：

# A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4.
# If all of the permutations are listed numerically or alphabetically, we call it lexicographic order.
# The lexicographic permutations of 0, 1 and 2 are: 012 021 102 120 201 210
# What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

permutations = []

def getLexicographicPermutationsOf(digits, state):
    if len(digits) == 0:
        permutations.append(str(state))

    for i in range(len(digits)):
        state.append(digits[i])
        rest = digits[:i] + digits[i+1:]
        getLexicographicPermutationsOf(rest, state)
        state.pop()

digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
getLexicographicPermutationsOf(digits, [])
print(permutations[999999])

我的第一个问题是关于yield语句的使用。我的第一个设计是用yield state替换permutations.append行，而不是在顶部定义排列列表。然后，我将该方法的返回值赋给一个变量。我检查了一下，不出所料，返回值是一个生成器。但是，循环遍历其内容表明没有生成任何值。我是不是漏掉了什么？

我的第二个查询是关于最后一行-从列表中打印一个值。当我运行它时，它输出值就好像它是一个列表，而它应该是一个字符串。实际上，用print(type(permutations[999999]))替换print(permutations[999999])会导致< class str>。那么，为什么它像列表一样打印(带有方括号，用逗号分隔)？

Answer 1

当您以递归方式调用getLexicographicPermutationsOf时，您也需要从那里生成结果。

for result in getLexicographicPermutationsOf(rest, state):
    yield result

permutations.append(str(state))创建了state的字符串表示，这是一个列表。这就解释了为什么它在打印时看起来像一个列表。

Answer 2

有一种计算量小得多的方法来计算它。实际上，编写程序可能并不那么容易，但它可以让您手动计算出答案。:) (提示:有多少个排列？其中有多少以0开头？)

此外，range(len(x))是高度非Pythonic式的。当然，如果有索引来切分列表来移除'current‘元素，那就好了。但是还有另一种方法:只需让Python删除具有该值的元素(因为只有一个这样的元素)。这允许我们直接循环元素值：

for digit in digits:
    state.append(digit)
    rest = digits[:]
    rest.remove(digit) # a copy with the current value removed.
    getLexicographicPermutationsOf(rest, state)
    state.pop()

range主要用于实际创建数据范围-例如使用初始化digits。:)

我是不是漏掉了什么？

你没有意识到仅仅是递归调用一个函数并不能神奇地把结果放在任何地方。事实上，即使你“产生”递归调用的结果，它仍然不会做你想要的事情--你最终会得到一个返回生成器的生成器(返回生成器，等等……当你想要一个生成器的时候)。(FogleBird的答案解释了如何处理这个问题:您必须从递归调用中获取生成器，并显式地将其生成的元素“馈送”到当前生成器中。)

但无论如何，还有一种更简单的方法:库中已经内置了这个算法。

整个程序可以这样完成：

from itertools import permutations, islice
print next(islice(permutations(range(10)), 1000000, None))

为什么它像列表一样打印(带有方括号，用逗号分隔)？

因为字符串包含方括号和逗号。这就是在列表(本例中为state)上使用str时所得到的结果。