Python 列表与生成器

Question

我有一个关于Project Euler第24题的（正确的）解决方案。我对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这个语句。最开始，我的设计是把定义permutations列表的部分去掉，直接用yield state来替代permutations.append。然后我会把这个方法的返回值赋给一个变量。我检查了一下，返回值果然是一个生成器，没问题。但是，当我尝试遍历它的内容时，发现没有生成任何值。我是不是漏掉了什么？

我第二个问题是关于最后一行 - 从列表中打印一个值。当我运行这段代码时，输出的值看起来像是一个列表，而实际上它应该是一个字符串。事实上，把print(permutations[999999])替换成print(type(permutations[999999]))后，结果显示< class str>。那么为什么它会像列表那样打印出来（用方括号括起来，并用逗号分隔）呢？

Answer 1

有一种计算方法要简单得多。虽然写程序可能不太容易，但你可以手动算出答案。:)（提示：有多少种排列？其中有多少种是以0开头的？）

另外，range(len(x)) 在Python中并不是一个很好的写法。虽然有时需要索引来切片列表以去掉“当前”元素，但其实有另一种方法：直接让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。:)

我是不是漏掉了什么？

你漏掉了一个点：单纯地递归调用一个函数并不会自动把结果放到任何地方。实际上，即使你在递归调用中使用了 'yield'，结果也不会如你所愿——你最终会得到一个生成器，它返回的是生成器（这些生成器又返回生成器，等等……一直到递归的最底层），而你其实只想要一个生成器。（FogleBird的回答解释了如何处理这个问题：你必须从递归调用中获取生成器，并明确地把它产生的元素“喂”给当前的生成器。）

不过其实有更简单的方法：库里已经内置了这个算法。

整个程序可以这样写：

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

为什么打印出来的像个列表（带方括号，用逗号分隔）？

因为字符串里包含了方括号和逗号。这就是你对一个列表（在这个例子中是 state）使用 str 时得到的结果。

Answer 2

当你递归调用 getLexicographicPermutationsOf 这个函数时，你也需要从那里返回结果。

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

permutations.append(str(state)) 这行代码是把 state 这个列表转换成字符串形式。这样做的原因就是当你打印出来的时候，它看起来像一个列表。