使用Itertools的内部中断嵌套循环变量

Question

有经验的开发人员学习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循环，使用递归或迭代。编码之前，我谷歌搜索，发现this thread看起来很有前途。

所以现在我有：

from itertools import product, repeat 
set = range(n) 
sets = repeat(set, k) 

for subset in list(product(*sets)) : 
    doSomethingWith(subset) 

精美Python的，但我仍然有同样的问题。我没有办法告诉product（）什么时候打破最内层的循环。我真正想要的是能够将一个回调函数传递到product（）中，以便它可以执行并可选地跳出最内层循环。

任何Pythonic建议？我讨厌必须显式编码变量嵌套循环，或者迭代product（）返回并手工检查子集。这似乎是如此老派:-)

Answer 1

这是一个有趣的问题。我炮制了一个可以用来实现你想要的东西的生成器。这比完整的解决方案更像是一个原型。可能需要调整才能真正有用，并且可能存在我没有考虑过的边缘案例。 （对于一两件事，现在它将无法正常对可能枯竭型，只有重新iterables如列表任意iterables工作）。

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)不会有任何效果，因为它只是意味着“跳到最内层迭代器的下一个迭代”，这是常规迭代无论如何会做的。

与使用类似product或combinations从itertools之类的解决方案相比，此优势在于您无法阻止那些生成器生成每个组合。所以，即使你想跳过一些元素，itertools仍然会执行所有循环来生成所有你不想要的元素，并且只有在它们已经生成后才会丢弃它们。另一方面，这个breakableProduct，实际上如果你告诉它会退出内部循环，所以它会完全跳过不必要的迭代。

Answer 2

这是一个相当基本的迭代有序组合制造商，它采用回调函数。它不像BrenBarn的解决方案那样具有多功能性，但它确实跳过了产生如问题中指定的产品：如果回传失败时，如果通过参数seq，返回False（或者false-ish），那么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线会产生所有组合。

---

此代码可以很容易地修改为做更大的跳过。我们不用回调函数中的布尔返回值，而是返回所需的跳转级别。如果它返回零，那么我们不会做任何跳过。如果它返回1，那么我们跳过以上述版本开头的子序列seq[:-1]。如果回调返回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)