Переменные уровни вложенных циклов с внутренними разрывами с использованием Itertools

Question

Опытный разработчик, изучающий Python.

Я выполняю итерацию через комбинации k за раз из списка размера n. Я использую

from itertools import chain, combinations 
for subset in (combinations(range(n), k)) : 
    doSomethingWith(subset) 

Теперь проблема заключается в том, что большую часть времени мой doSomethingWith() 's не являются продуктивными, и я хотел бы, чтобы пропустить как многие из них, как я могу. И если doSomthingWith() терпит неудачу для данного подмножества, я могу пропустить каждое подмножество, самая правая координата которого больше. Другими словами, если это не удается для (1,3,5,8), то следующее подмножество, на которое я хочу обратить внимание, это (1,3,6,0), пропуск (1,3,5,9), (1, 3,5,10) и т. Д.

Я понял, что мне нужно получить явный контроль индексов цикла. Мне нужно переменное число вложенных циклов, используя рекурсию или итерацию. Перед тем, как кодировать это, я разобрался и нашел this thread, который выглядит многообещающим.

Так что теперь у меня есть:

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

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

Красиво вещий, но я до сих пор с той же проблемой. У меня нет возможности сказать product(), когда вырваться из самого внутреннего цикла. Я действительно хочу, чтобы иметь возможность передать функцию обратного вызова в product(), чтобы он мог выполнять и, возможно, выходить из самого внутреннего цикла.

Любые предложения Pythonic? Мне не хотелось бы явно указывать переменные вложенные циклы или перебирать результат из product() и проверять подмножества вручную. Это кажется такой старой школой :-)

Answer 1

Это интригующая проблема. Я придумал генератор, который можно использовать для достижения чего-то вроде того, что вы хотите. Это скорее прототип, чем полное решение. Возможно, его нужно будет настроить, чтобы быть действительно полезным, и могут быть случаи, которые я не рассматривал. (С одной стороны, сейчас он не будет работать должным образом на произвольном итерируемых, которые могут быть exhaused, только на повторном итерируемом как списки.)

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, но оно пропускает генерирующие продукты, как указано в вопросе: если обратный вызов сбой при передаче arg seq, возвращающий 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)