使用生成器生成排列

Question

我正在编写一个程序来生成字符串的所有排列：

def print_permutations_wrapper(str):
    strList = str.split()
    print_permutations(strList, 0, len(strList))


def print_permutations(strList: list, start: int, end: int):
    if start >= end - 1:
        print(strList)
        return

    print_permutations(strList, start+1, end)
    for i in range(start+1, end):
        strList[start], strList[i] = strList[i], strList[start]
        print_permutations(strList, start+1, end)
        strList[i], strList[start] = strList[start], strList[i]


def main():
    str = 'a b c'
    print_permutations_wrapper(str)


if __name__ == "__main__":
    main()

它工作正常，但我不想打印它，而是想 return 它懒惰地使用 yield:

def print_permutations_wrapper(str):
    strList = str.split()
    yield from print_permutations(strList, 0, len(strList))


def print_permutations(strList: list, start: int, end: int):
    if start >= end - 1:
        yield strList
        return

    yield from print_permutations(strList, start+1, end)
    for i in range(start+1, end):
        strList[start], strList[i] = strList[i], strList[start]
        yield from print_permutations(strList, start+1, end)
        strList[i], strList[start] = strList[start], strList[i]


def main():
    str = 'a b c'
    x = print_permutations_wrapper(str)
    print(list(x))

if __name__ == "__main__":
    main()

我得到的输出是：

[['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c'], ['a', 'b', 'c']]

而不是所有排列。
如何纠正这个？

我正在使用 Python 3.7.

Answer 1

使用你的第二个程序，但添加一个 print(strList) 将显示生成器函数产生了你预期的结果，但最终输出显然不是你预期的。这是因为结构化程序采用列表，但对同一副本执行所有操作（假设限制内存使用）。您也可以通过

验证这一点

>>> strList = ['a', 'b', 'c'] 
>>> items = list(print_permutations(strList, 0, 3))
>>> items[0] is items[1]
True
>>> items[0] is strList
True

很明显，items 中的每个项目都与传入的原始 strList 相同。考虑到问题的简单性，可以通过生成列表的浅表副本来避免这种情况反而。因此函数的相关 yield 部分将变为

def print_permutations(strList: list, start: int, end: int):
    if start >= end - 1:
        yield list(strList)
        return

现在运行它应该产生：

>>> strList = ['a', 'b', 'c'] 
>>> items = list(print_permutations(strList, 0, 3))
>>> items[0] is items[1]
False

此外，顺便说一句，排列实际上是标准库的一部分，可通过 itertools.permutation.

获得

相关："Least Astonishment" and the Mutable Default Argument

使用生成器生成排列

Generating permutations using generators

python

iterator

yield

generator

permutation