Есть ли способ превратить этот вложенный цикл в рекурсивный цикл?

Question

Я ищу помощь по следующей проблеме.У меня есть небольшая программа, которая является частью гораздо более крупной программы, мне нужно пройтись по каждой комбинации массива чисел от 1 до 10 (может быть, больше или меньше) так же, как работает itertools.Однако, поскольку у меня есть определенные ограничения, мне нужно пропустить большое количество этих комбинаций, чтобы сэкономить время, поскольку это потенциально может стать очень большим.

Вот моя программа

combination = [-1, -1, -1, -1]
len_combination = len(combination)

max_at_index = [0, 2, 2, 1, 2, 1, 2, 1, 3, 1]
len_index = len(max_at_index)

end = 0


def skip(depth):

    combination[depth] = combination[depth] + 1
    if combination[depth] == len_index:
        combination[depth] = 0

    for x in range(0, len_index):
        if combination[:depth + 1].count(x) > max_at_index[x]:

            return True

    return False


for i in range(0, len_index):

    if skip(0):
        continue

    for j in range(0, len_index):

        if skip(1):
            continue

        for k in range(0, len_index):

            if skip(2):
                continue

            for l in range(0, len_index):

                if skip(3):
                    continue

                print(combination)

Этопример имеет 4 элемента, каждый цикл от 0 до 9 (([0, 0, 0, 0] до [9, 9, 9, 9]).Однако моя переменная max_at_index ограничивает количество значений, разрешенных в массиве для каждого индекса.Здесь нам разрешено 0 0, 2 1 с, 2 2 с, 1 3 с и т. Д. Это работает хорошо, и я могу даже расширить или сжать массив max_at_index.

Что я не могу понять, как сделать, это сделать вложенныйдля цикла рекурсивного, так что я могу увеличить или уменьшить размер комбинации, чтобы иметь больше или меньше элементов.

Заранее спасибо.

РЕДАКТИРОВАТЬ: В соответствии с просьбой, некоторые объяснения моей логики

Рассмотрим следующий список расходов

[
[1, 2, 3, 4, 5, 6, 0, 8, 9],
[10, 11, 12, 0, 14, 15, 16, 17, 18, 19],
[0, 21, 22, 23, 24, 25, 26, 27, 28, 29],
[30, 0, 32, 33, 34, 35, 0, 37, 38, 0]
]

Я должен сгенерировать наименьшую возможную сумму при выборе одного числа из каждого массива, где ...

• Число от каждогомассив не может быть 0
• Индекс каждого выбранного числа не может превышать заданный предел (т. е. не более 3 из индекса 2)
• Количество номеров, выбранных из индекса 0, должно достигатьпредел (например, 2 должен исходить из индекса 0) или следующий максимально возможный.

Эту часть я тоже выяснил.Если я повторю каждую возможную комбинацию от 0,0,0,0 до 9,9,9,9, я могу проверить, соответствует ли она вышеуказанному.Мне просто нужно избегать зацикливания каждой комбинации, так как большинство из них будет бесполезным, и оно станет большим

Answer 1

Я думаю, что это одна из возможных реализаций:

def bounded_comb(max_at_index, n):
    yield from _bounded_comb_rec(max_at_index, n, [0] * len(max_at_index), [])

def _bounded_comb_rec(max_at_index, n, counts, current):
    # If we have enough elements finish
    if len(current) >= n:
        yield tuple(current)
    else:
        # For each index and max
        for idx, m in enumerate(max_at_index):
            # If the max has not been reached
            if m > counts[idx]:
                # Add the index
                counts[idx] += 1
                current.append(idx)
                # Produce all combinations
                yield from _bounded_comb_rec(max_at_index, n, counts, current)
                # Undo add the index
                current.pop()
                counts[idx] -= 1

# Test
max_at_index = [0, 2, 1, 3]
n = 4
print(*bounded_comb(max_at_index, n), sep='\n')

Вывод:

(1, 1, 2, 3)
(1, 1, 3, 2)
(1, 1, 3, 3)
(1, 2, 1, 3)
(1, 2, 3, 1)
(1, 2, 3, 3)
(1, 3, 1, 2)
(1, 3, 1, 3)
(1, 3, 2, 1)
(1, 3, 2, 3)
(1, 3, 3, 1)
(1, 3, 3, 2)
(1, 3, 3, 3)
(2, 1, 1, 3)
(2, 1, 3, 1)
(2, 1, 3, 3)
(2, 3, 1, 1)
(2, 3, 1, 3)
(2, 3, 3, 1)
(2, 3, 3, 3)
(3, 1, 1, 2)
(3, 1, 1, 3)
(3, 1, 2, 1)
(3, 1, 2, 3)
(3, 1, 3, 1)
(3, 1, 3, 2)
(3, 1, 3, 3)
(3, 2, 1, 1)
(3, 2, 1, 3)
(3, 2, 3, 1)
(3, 2, 3, 3)
(3, 3, 1, 1)
(3, 3, 1, 2)
(3, 3, 1, 3)
(3, 3, 2, 1)
(3, 3, 2, 3)
(3, 3, 3, 1)
(3, 3, 3, 2)

Answer 2

sympy также предоставляет все необходимое:

from sympy.utilities.iterables import multiset_permutations


max_at_index = [0, 2, 2, 1, 2, 1, 2, 1, 3, 1]
m_set = {i: n for  i, n in enumerate(max_at_index) if n != 0}

for perm in multiset_permutations(m_set, 4):
    print(perm)

---

Объяснение:

тип данных, на котором это основано, является мультимножеством (т.е. набор, в котором элементы могут появляться более одного раза, но порядок не имеет значения).есть функция для такой структуры данных в sympy: sympy.utilities.iterables.multiset

from itertools import chain
from sympy.utilities.iterables import multiset

max_at_index = [0, 2, 2, 1, 2, 1, 2, 1, 3, 1]
m_set = multiset(chain.from_iterable(n * [i] for i, n in enumerate(max_at_index)))
# {1: 2, 2: 2, 3: 1, 4: 2, 5: 1, 6: 2, 7: 1, 8: 3, 9: 1}

на самом деле multiset просто возвращает dict;поэтому это проще:

m_set = {i: n for  i, n in enumerate(max_at_index) if n != 0}
# {1: 2, 2: 2, 3: 1, 4: 2, 5: 1, 6: 2, 7: 1, 8: 3, 9: 1}

к счастью sympy также имеет методы для перестановки и объединения этих мультимножеств без генерации повторений:

from sympy.utilities.iterables import multiset_permutations

for perm in multiset_permutations(m_set, 4):
    print(perm)

Чтобы помочь с распараллеливанием, сначала может помочь расчет комбинаций:

from sympy.utilities.iterables import multiset_combinations, multiset_permutations

for comb in multiset_combinations(m_set, 4):
    print()
    for perm in multiset_permutations(comb):
        print(perm)

, который производит (добавляет пробел после каждой новой комбинации)

[1, 1, 2, 2]
[1, 2, 1, 2]
[1, 2, 2, 1]
[2, 1, 1, 2]
[2, 1, 2, 1]
[2, 2, 1, 1]

[1, 1, 2, 3]
[1, 1, 3, 2]
[1, 2, 1, 3]
[1, 2, 3, 1]
[1, 3, 1, 2]
[1, 3, 2, 1]
[2, 1, 1, 3]
[2, 1, 3, 1]
[2, 3, 1, 1]
[3, 1, 1, 2]
[3, 1, 2, 1]
[3, 2, 1, 1]

...

[8, 8, 8, 9]
[8, 8, 9, 8]
[8, 9, 8, 8]
[9, 8, 8, 8]

Answer 3

Я не хотел показывать что-нибудь причудливое, но дать вам самый простой ответ для рекурсивного цикла (так как это был ваш вопрос)

combination = [-1, -1, -1, -1]
len_combination = len(combination)
max_depth = 3
max_at_index = [0, 2, 2, 1, 2, 1, 2, 1, 3, 1]
len_index = len(max_at_index)

end = 0

def skip(depth):

    combination[depth] = combination[depth] + 1
    if combination[depth] == len_index:
        combination[depth] = 0

    for x in range(0, len_index):
        if combination[:depth + 1].count(x) > max_at_index[x]:

            return True,combination # Needs to return the state of combination

    return False,combination # Needs to return the state of combination

def loop(depth,combination):
    if depth == max_depth:
        boolean, combination = skip(depth)
        if not(boolean):
            print (combination)
            return combination
    else:
        for i in range(0, len_index):
            boolean, combination = skip(depth)
            if not(boolean):
                loop(depth+1,combination)

loop(0,combination)

Answer 4

это попытка, где я ограничиваю создание пула значений для выбора (select_from), а затем создаю combinations:

from itertools import chain, combinations

max_at_index = [0, 2, 2, 1, 2, 1, 2, 1, 3, 1]

select_from = list(chain.from_iterable(n * [i] for i, n in enumerate(max_at_index)))
# [1, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 8, 9]

for comb in combinations(select_from, 4):
    print(comb)

это производит отсортированные комбинации. если вам также нужны все перестановки, вам нужно сделать это потом (я использую set 'seen' здесь, чтобы избежать дублирования):

from itertools import chain, combinations, permutations

seen_comb = set()

select_from = list(chain.from_iterable(n * [i] for i, n in enumerate(max_at_index)))

for comb in combinations(select_from, 4):

    sorted_comb = tuple(sorted(comb))
    if sorted_comb in seen_comb:
        continue
    seen_comb.add(sorted_comb)

    seen_perm = set()

    for perm in permutations(comb):
        if perm in seen_perm:
            continue
        seen_perm.add(perm)

        print(perm)