python - 是否有替代 python 生成器输入排列的方法？

Question

我正在尝试在 itertools.permutations 中使用无限生成器，但它似乎不起作用。永远不会创建返回生成器，因为该函数会永远运行。要理解我的意思，请考虑:

from itertools import count, permutations
all_permutations = permutations(count(1), 4)

我想象它的工作方式是它生成前 4 个自然数的所有可能的 4 长度排列。然后它应该生成前 5 个自然数的所有可能的 4 长度排列，没有重复，所以 5 必须包含在所有这些中。但是发生的是 python 卡在创建 all_permutations 上。

在我开始并从头开始创建自己的函数之前，我想知道是否有另一个库可以实现我正在寻找的功能？另外，这里的内置函数不应该能够处理这个吗？这可能是一个应该解决的错误吗？

编辑:对于一些迭代......

1 2 3 4
1 2 4 3
...
4 3 2 1
1 2 3 5
1 2 5 3
...
5 3 2 1
1 2 4 5
1 2 5 4
...

Answer 1

好问题!这是一种系统地生成它们的有效方法，无需重复(也无需检查):

1. 首先是前n个元素的排列；
2. 然后是涉及第n+1个元素和前面元素的n-1的排列；
3. 然后是第 n+2 个元素和前面的 n-1 元素，等等。

换句话说，最后绘制的元素总是包含在当前批处理中。这只会保留一个已消耗源元素的元组(这是不可避免的，因为我们将继续在排列中使用所有这些元素)。

如您所见，我稍微简化了实现:我用 n-1 元素初始化 base 并直接进入主循环，而不是第 1 步.

from itertools import islice, permutations, combinations

def step_permutations(source, n):
    """Return a potentially infinite number of permutations, in forward order"""

    isource = iter(source)
    # Advance to where we have enough to get started
    base = tuple(islice(isource, n-1))

    # permutations involving additional elements:
    # the last-selected one, plus <n-1> of the earlier ones
    for x in isource:
        # Choose n-1 elements plus x, form all permutations
        for subset in combinations(base, n-1):
            for perm in permutations(subset + (x,), n):
                yield perm

        # Now add it to the base of elements that can be omitted 
        base += (x,)

演示:

>>> for p in step_permutations(itertools.count(1), 3):
    print(p)

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
(1, 2, 4)
(1, 4, 2)
(2, 1, 4)
(2, 4, 1)
(4, 1, 2)
(4, 2, 1)
(1, 3, 4)
(1, 4, 3)
(3, 1, 4)
(3, 4, 1)
(4, 1, 3)
(4, 3, 1)
(2, 3, 4)
(2, 4, 3)
(3, 2, 4)
...