问题描述
经验丰富的开发人员学习Python。
我一次从大小为n的列表中遍历组合k。 我一直在用
from itertools import chain, combinations
for subset in (combinations(range(n), k)) :
doSomethingWith(subset)
现在的问题是，大多数时候，我的doSomethingWith（）都不高效，我想尽可能多地跳过它们。 如果doSomthingWith（）对于给定的子集失败，我可以跳过最右边坐标较大的每个子集。 换句话说，如果它失败了（1,3,5,8），那么我要查看的下一个子集是（1,3,6,0），跳过（1,3,5,9），（1， 3,5,10）等
我意识到我需要对循环索引进行显式控制。 我需要使用递归或迭代的可变数量的嵌套for循环。 在进行编码之前，我在Google周围搜索，发现看起来很有希望。
所以现在我有：
from itertools import product, repeat
set = range(n)
sets = repeat(set, k)
for subset in list(product(*sets)) :
doSomethingWith(subset)
漂亮的Pythonic，但我仍然有同样的问题。 我没有办法告诉product（）何时脱离最内层的循环。 我真正想要的是能够将回调函数传递给product（），以便它可以执行并有选择地冲出最里面的循环。
有Pythonic建议吗？ 我讨厌必须显式地编写变量嵌套循环的代码，或者遍历product（）的返回并手动检查子集。 似乎太老了:-)
1楼
这是一个有趣的问题。 我设计了一个生成器，可以用来实现您想要的东西。 这不仅仅是完整的解决方案，而是更多的原型。 可能需要对其进行调整才能真正有用，并且可能存在一些我没有考虑过的情况。 （一方面，目前它无法在可能用尽的任意可迭代对象上正常工作，仅在列表等可迭代对象上起作用。）
class SkipUp(Exception):
def __init__(self, numSkips):
self.numSkips = numSkips
super(SkipUp, self).__init__(numSkips)
def breakableProduct(*sets):
if not sets:
yield []
return
first, rest = sets[0], sets[1:]
for item in first:
subProd = breakableProduct(*rest)
for items in subProd:
try:
yield [item] + items
except SkipUp as e:
if e.numSkips == 0:
yield None
break
else:
e.numSkips -= 1
yield subProd.throw(e)
您可以使用breakableProduct或多或少像正常itertools.product ：
>>> prod = breakableProduct([1, 2, 3], [11, 22, 33], [111, 222, 333])
... for x, y, z in prod:
... print(x, y, z)
1 11 111
1 11 222
1 11 333
1 22 111
1 22 222
# ...etc...
3 33 222
3 33 333
但是，从中获取值后，如果希望使用.throw可以传入SkipUp异常，该异常的参数是要跳过其下一个元素的集合的索引。
也就是说，如果您要跳过第三组的所有元素并跳到第二组的下一个元素，请使用SkipUp(1) （1是第二组，因为索引是基于0的）：
>>> prod = breakableProduct([1, 2, 3], [11, 22, 33], [111, 222, 333])
... for x, y, z in prod:
... print(x, y, z)
... if z == 222:
... prod.throw(SkipUp(1))
1 11 111
1 11 222
1 22 111
1 22 222
1 33 111
1 33 222
2 11 111
2 11 222
2 22 111
2 22 222
2 33 111
2 33 222
3 11 111
3 11 222
3 22 111
3 22 222
3 33 111
3 33 222
看看这如何在222之后中止最内层的迭代，而不是跳转到中间生成器的下一个迭代。
如果要一直跳到最外层迭代：
>>> prod = breakableProduct([1, 2, 3], [11, 22, 33], [111, 222, 333])
... for x, y, z in prod:
... print(x, y, z)
... if z == 222:
... prod.throw(SkipUp(0))
1 11 111
1 11 222
2 11 111
2 11 222
3 11 111
3 11 222
所以SkipUp(0)跳到第一个迭代器的下一个“滴答”（即列表[1, 2, 3] ）。
抛出SkipUp(2)不会有任何效果，因为这仅表示“跳到最里面的迭代器的下一个迭代”，这是常规迭代无论如何都会做的。
与使用itertools product或combinations类的解决方案相比，此方法的优势在于，您不能阻止这些生成器生成所有组合。
因此，即使您想跳过某些元素，itertools仍将执行所有循环以生成所有不需要的元素，并且仅在它们生成后将其丢弃。
这breakableProduct ，在另一方面，实际上退出内环早期，如果你告诉它，所以它会完全跳过不必要的迭代。
2楼
这是一个相当基本的迭代有序组合器，它具有回调函数。
它不像BrenBarn的解决方案那样通用，但是它确实跳过了问题中指定的生成乘积：如果在传递arg seq时回调失败，返回False （或假的东西），那么combo将跳过生成以以下开头的其他子序列seq[:-1] 。
def combo(n, k, callback):
a = list(range(k))
ok = callback(a)
k -= 1
while True:
i = k
if not ok: i -= 1
while True:
a[i] += 1
if a[i] == (n + i - k):
i -= 1
if i < 0:
return
else:
break
v = a[i] + 1
a[i+1:] = range(v, v + k - i)
ok = callback(a)
# test
n = 8
k = 4
def do_something(seq):
s = sum(seq)
ok = s <= seq[-2] * 3
print(seq, s, ok)
return ok
combo(n, k, do_something)
产量
[0, 1, 2, 3] 6 True
[0, 1, 2, 4] 7 False
[0, 1, 3, 4] 8 True
[0, 1, 3, 5] 9 True
[0, 1, 3, 6] 10 False
[0, 1, 4, 5] 10 True
[0, 1, 4, 6] 11 True
[0, 1, 4, 7] 12 True
[0, 1, 5, 6] 12 True
[0, 1, 5, 7] 13 True
[0, 1, 6, 7] 14 True
[0, 2, 3, 4] 9 True
[0, 2, 3, 5] 10 False
[0, 2, 4, 5] 11 True
[0, 2, 4, 6] 12 True
[0, 2, 4, 7] 13 False
[0, 2, 5, 6] 13 True
[0, 2, 5, 7] 14 True
[0, 2, 6, 7] 15 True
[0, 3, 4, 5] 12 True
[0, 3, 4, 6] 13 False
[0, 3, 5, 6] 14 True
[0, 3, 5, 7] 15 True
[0, 3, 6, 7] 16 True
[0, 4, 5, 6] 15 True
[0, 4, 5, 7] 16 False
[0, 4, 6, 7] 17 True
[0, 5, 6, 7] 18 True
[1, 2, 3, 4] 10 False
[1, 2, 4, 5] 12 True
[1, 2, 4, 6] 13 False
[1, 2, 5, 6] 14 True
[1, 2, 5, 7] 15 True
[1, 2, 6, 7] 16 True
[1, 3, 4, 5] 13 False
[1, 3, 5, 6] 15 True
[1, 3, 5, 7] 16 False
[1, 3, 6, 7] 17 True
[1, 4, 5, 6] 16 False
[1, 4, 6, 7] 18 True
[1, 5, 6, 7] 19 False
[2, 3, 4, 5] 14 False
[2, 3, 5, 6] 16 False
[2, 3, 6, 7] 18 True
[2, 4, 5, 6] 17 False
[2, 4, 6, 7] 19 False
[2, 5, 6, 7] 20 False
[3, 4, 5, 6] 18 False
[3, 4, 6, 7] 20 False
[3, 5, 6, 7] 21 False
[4, 5, 6, 7] 22 False
如果您将“ if not ok: i -= 1注释掉if not ok: i -= 1行，它将产生所有组合。
可以轻松修改此代码以进行更大的跳过。
与其从回调中使用布尔返回值，不如让我们返回想要的跳过级别。
如果它返回零，那么我们不做任何跳过。
如果返回1，则与上述版本一样，我们跳过以seq[:-1]的子序列。
如果回调返回2，则我们跳过以seq[:-2]等seq[:-2]的子序列。
def combo(n, k, callback):
a = list(range(k))
skips = callback(a)
k -= 1
while True:
i = k - skips
while True:
a[i] += 1
if a[i] == (n + i - k):
i -= 1
if i < 0:
return
else:
break
v = a[i] + 1
a[i+1:] = range(v, v + k - i)
skips = callback(a)