Как выйти из цикла for (python)

Question

Есть цикл, он перебирает все комбинации чисел из списка (lst2), методом itertools.combinations_with_replacement.

Цель получить последовательность чисел с сумой элементов равной "длинне" - width (200 в данном случае) и что бы в выдаче был первый из запрошенных форматов (обозначено formats[0], в данном случае 50).

Код выдает:

(50, 150) (50, 50, 100) (50, 55, 95) (50, 60, 90) (50, 65, 85) (50, 70, 80) (50, 75, 75) (50, 50, 50, 50)

Что полностью соответствует задаче.

Проблема в том что цикл не останавливается так как не перебрал все возможные комбинации.

Подскажите пожалуйста как я могу из него выйти сохранив при этом нужные мне значения. Благодарю, код ниже.

from itertools import *

width = 200 # Длинна материала 

lst2 =  [50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120, 125, 130, 135, 140, 145, 150, 155, 160, 165, 170, 175, 180, 185, 190, 195] # Возможные форматы

formats = [50, 60] # Форматы которые должны быть в выдаче

lst3 = [] #Список в который записываются трушные варианты

for i in range(1, len(lst2) + 1):
    for a in combinations_with_replacement(lst2, i):
        if formats[0] in a and sum(a) == width:
            print(a)
            lst3 = lst3 + [str(a)]
        else:
            pass

Answer 1

Если вам нужно только первое значение, то остановиться можно так:

for i in range(1, len(lst2) + 1):
    for a in combinations_with_replacement(lst2, i):
        if formats[0] in a and sum(a) == width:
            lst3.append(a)
            break
    else:
        continue
    break

print(lst3)

Если нужно больше, то делаете первый break по достижению нужной len(lst3).

Answer 2

Комбинаторные итераторы не пригодны для комбинаторного поиска. Они порождают огромное количество вариантов, из которых можно выбрать подходящие, но сам процесс отбора долгий. С другой стороны, если вы строите комбинации вручную, вы можете отбрасывать негодные варианты пачками.

В вашей задаче все числа в списке больше нуля и поиск можно останавливать как только сумма отобранных размеров превысила искомую. Это драматически сокращает пространство поиска.

def variants(sizes, target):

    def search(solution, i, target):
        assert target >= 0

        if target == 0:

            def unwrap(node):
                while node is not None: 
                    size, tail = node
                    yield size
                    node = tail

            yield tuple(unwrap(solution))[::-1]
            return

        if i >= len(sizes):
            return

        size = sizes[i]
        yield from search(solution, i + 1, target) 
        for k in range(1, target // size + 1):
            solution = size, solution
            target -= size
            yield from search(solution, i + 1, target)

    return search(None, 0, target)


def main():
    width = 200 # длина материала 

    sizes = [
        50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115,
        120, 125, 130, 135, 140, 145, 150, 155, 160, 165, 170, 175,
        180, 185, 190, 195
    ] # возможные форматы

    formats = [50, 60] # форматы которые должны быть в выдаче

    for v in variants(sizes, width):
        if any(f in v for f in formats):
            print(v)


main()

$ python search.py
(60, 140)
(60, 70, 70)
(60, 65, 75)
(60, 60, 80)
(55, 60, 85)
(50, 150)
(50, 75, 75)
(50, 70, 80)
(50, 65, 85)
(50, 60, 90)
(50, 55, 95)
(50, 50, 100)
(50, 50, 50, 50)

Этот код работает мгновенно, потому что он просматривает только 4144 варианта, отбирает из них 26, из которых затем отбирается 13.

Для сравнения ваш код пытается перебрать 118264581564861423 варианта. При условии перебора одного миллиона комбинаций в секунду на перебор уйдёт примерно четыре тысячи лет.

БЛОГ НА HUSL

Как выйти из цикла for (python)

Ответы (2 шт):