我正在解决一个涉及组合的编程难题。它让我找到了一个很棒的 itertools.combinations
函数,我想知道它是如何工作的。文档说该算法大致等同于以下内容:
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
我的想法是:我们从最明显的组合开始(r
第一个连续元素)。然后我们更改一个(最后一个)项目以获得每个后续组合。
我正在努力解决的问题是 for
循环中的条件。
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
这个表达式非常简洁,我怀疑这是所有魔法发生的地方。请给我一个提示,以便我弄明白。
最佳答案
循环有两个目的:
- 如果到达最后一个索引列表则终止
- 确定索引列表中可以合法增加的最右边的位置。然后,此位置是将所有索引重置到右侧的起点。
假设您有一个超过 5 个元素的可迭代对象,并且想要长度为 3 的组合。为此,您本质上需要的是生成索引列表。上述算法的有趣部分从当前索引列表生成下一个这样的索引列表:
# obvious
index-pool: [0,1,2,3,4]
first index-list: [0,1,2]
[0,1,3]
...
[1,3,4]
last index-list: [2,3,4]
i + n - r
是索引列表中索引 i
的最大值:
index 0: i + n - r = 0 + 5 - 3 = 2
index 1: i + n - r = 1 + 5 - 3 = 3
index 2: i + n - r = 2 + 5 - 3 = 4
# compare last index-list above
=>
for i in reversed(range(r)): if indices[i] != i + n - r: break else: break
这将在当前索引列表中向后循环,并在第一个不保持其最大索引值的位置停止。如果所有位置都保持其最大索引值,则没有进一步的索引列表,因此 return
。
在 [0,1,4]
的一般情况下,可以验证下一个列表应该是 [0,2,3]
。循环在位置1
处停止,后续代码
indices[i] += 1
增加 indeces[i]
的值 (1 -> 2
)。最后
for j in range(i+1, r): indices[j] = indices[j-1] + 1
将所有位置 > i
重置为最小的合法索引值,每个 1
都比其前身大。
关于python - Python 中 itertools.combinations 的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41694722/