我正在尝试在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/