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(permutations[999999]) 替换为 print(type(permutations[999999])) 会导致 <类str>。那么为什么它像列表一样打印（带有方括号，用逗号分隔）？

Answer 1

当您递归调用 getLexicgraphicPermutationsOf 时，您也需要从那里产生结果。

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

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

Answer 2

有一种计算强度较小的方法来计算此值。编写程序实际上可能并不那么容易，但它可以让您手动计算出答案。 :) （提示：有多少种排列？其中有多少是从 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。 :)

我在这里遗漏了什么吗？

您错过了仅递归调用函数不会神奇地将其结果放在任何地方。事实上，即使你“产生”递归调用的结果，它仍然不会做你想做的事 - 你最终会得到一个返回生成器的生成器（返回生成器等......直到当您需要一个生成器时，递归的基础）。 （FogleBird 的答案解释了如何处理这个问题：您必须从递归调用中获取生成器，并显式地将其生成的元素“馈送到”当前生成器中。）

但无论如何，还有一种更简单的方法：库已经构建了此算法 整个程序

可以这样完成：

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

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

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