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

Question

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

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

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

时挂起

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

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

Answer 1

像这样：

from itertools import count, permutations

def my_permutations(gen, n=4):
    i = iter(gen)
    population = []
    seen = set()
    while True:
        for p in permutations(population, n):
            if p not in seen:
                yield p
                seen.add(p)
        population.append(next(i))

请注意，内存使用量一直在增长，但据我所知，没有办法解决这个问题。

更高效的版本：

def my_permutations(gen, n=4):
    i = iter(gen)
    population = []
    while True:
        population.append(next(i))
        *first, last = population
        perms = permutations(first, n-1)
        yield from (p[:i] + (last,) + p[i:] for p in perms for i in range(n))

Answer 2

好问题！这是一种系统地生成它们的有效方法，无需重复（也无需检查）：

首先是前n个元素的排列；
然后排列涉及前面的第n+1个元素和n-1；
然后是第 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)
...

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

Is there an alternative to python's permutations for generator input?

python

generator

permutation

infinite

itertools