我正在尝试在itertools.permutations中使用无界生成器,但似乎无法正常工作。永远不会创建return生成器,因为该函数将永远运行。要理解我的意思,请考虑:

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
...

最佳答案

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

  • 首先是第一个n元素的排列;
  • ,然后是包括前面的n+1 st元素和n-1的排列
  • ,然后是涉及先前元素的n+2 nd元素和n-1的元素,等等。

  • 换句话说,绘制的最后一个元素始终包含在当前批次中。这只会保持消耗的源元素的元组(不可避免,因为我们将继续在排列中使用所有它们)。

    如您所见,我对实现进行了一些简化:代替了步骤1,我使用base元素初始化了n-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 - 生成器输入是否可以替代python的排列?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/46454108/

    10-13 06:02
    查看更多