Найти все комбинации из данного набора чисел, которые применяются к некоторым правилам

Question

Буду признателен за помощь в решении следующей проблемы:

У меня есть список чисел и словарь:

my_list = [400, 200, 100, 50, 25]
my_dict = {400: 8, 200:4, 100: 2, 50: 2, 25: 2}

Мне нужно найти все возможные комбинации, которые могут быть построены из чисел из my_list, когда они должны применять следующие правила:

1. Те же числа могут быть в комбинации ([400, 400, 400] является допустимой комбинацией)
2. Порядок не имеет значения ([400, 200, 100] для меня равно [100, 200, 400])
3. Сумма чисел в комбинации не должна превышать 1200
4. сумма my_dict[my_list_item] не должна превышает 24 (например, [400, 400, 400, 100] недопустимо, потому что my_dict[400]+my_dict[400]+my_dict[400]+my_dict[100] = 8+8+8+2 = 26, следовательно, это недопустимая комбинация)

Любые идеи для алгоритма python для решения этого. Спасибо

Answer 1

Предполагая, что вам нужен список «каждой комбинации вашего списка с повторением», я написал код, который вычисляет его.

Используется время l oop, которое увеличивается счетчик длины комбинации каждый раз. Поскольку длина комбинации может увеличиваться бесконечно, индикатор используется для остановки l oop, который активируется, когда не найдено ни одной комбинации.

from itertools import combinations_with_replacement

my_list = [400, 200, 100, 50, 25]
my_dict = {400: 8, 200:4, 100: 2, 50: 2, 25: 2}

final_list = []

combinationLength = 1
while True:
    c = list(combinations_with_replacement(my_list, combinationLength)) #generate every combination of length combinationLength
    countNextCombination = False #indicator to break the while loop

    for combination in c: 
        if (sum(combination) <= 1200):
            dicsum=0
            for j in combination:
                dicsum+=my_dict[j]
            if (dicsum<=24):
                final_list.append(list(combination))
                countNextCombination = True

    if countNextCombination == False: #if not a single combination was valid, finish the loop
        break
    combinationLength += 1

print (final_list)

Answer 2

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

#! /usr/bin/env python3

def combs (numbers, value_of, max_numbers=1200, max_value=24, min_i=0):
    if len(numbers) <= min_i:
        yield []
    else:
        for comb in combs(numbers, value_of, max_numbers, max_value, min_i+1):
            yield comb
            comb_copy = [n for n in comb] # Copy to avoid sharing bugs.
            numbers_sum = sum(comb)
            values_sum = sum([value_of[i] for i in comb])
            while True:
                comb_copy.append(numbers[min_i])
                numbers_sum += numbers[min_i]
                if max_numbers < numbers_sum:
                    break
                values_sum += value_of[numbers[min_i]]
                if max_value < values_sum:
                    break
                yield comb_copy


my_list = [400, 200, 100, 50, 25]
my_dict = {400: 8, 200:4, 100: 2, 50: 2, 25: 2}

for c in combs(my_list, my_dict):
    print(c)

Answer 3

Используя itertools, вам не понадобится рекурсивное решение. Итератор комбинаций комбинаций_символов предоставит вам комбинации, и вам нужно только проверить свои условия. Для вашего требования вам понадобится блок питания комбинаций (то есть комбинаций всех размеров):

например:

from itertools import combinations_with_replacement as combine

my_list = [400, 200, 100, 50, 25]
my_dict = {400: 8, 200:4, 100: 2, 50: 2, 25: 2}

for size in range(2,len(my_list)+1):
    for combo in combine(my_list, size):
        if sum(combo) <= 1200 \
        and sum(my_dict[c] for c in combo) <= 24:
            print(combo)

Вы можете поместите это в функцию и используйте yield combo вместо print(combo), если вы собираетесь каким-либо образом обрабатывать комбинации

output:

(400, 400)
(400, 200)
(400, 100)
(400, 50)
(400, 25)
...
(50, 50, 50, 50, 50)
(50, 50, 50, 50, 25)
(50, 50, 50, 25, 25)
(50, 50, 25, 25, 25)
(50, 25, 25, 25, 25)
(25, 25, 25, 25, 25)

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