Python - все комбинации списков с использованием сложения

Question

У меня есть список в этой форме: ["Name/num1/num2/num3/num4/num5", ...]

Например: available = ["a/1/2/3/4/5", "b/5/4/3/2/4", "c/4/3/2/1/3"]

Я пытаюсь создать все возможные комбинации элементов в available, гдесумма num5 каждого элемента в комбинации (например, for a is 5, for b is 1, for c is 5) меньше, чем MAXNUM (например, 3000).

Для пояснения примера, программасоздайте генератор для available и выше MAXNUM = 9, который можно преобразовать в следующий список:

[["a/1/2/3/4/5", "b/5/4/3/2/4"], ["a/1/2/3/4/5", c/4/3/2/1/3], [b/5/4/3/2/4, b/5/4/3/2/4], [b/5/4/3/2/4, "c/4/3/2/1/3"], ["c/4/3/2/1/3", "c/4/3/2/1/3", "c/4/3/2/1/3"]]

Примечание. Этот код должен возвращать результат с available, имеющим100 предметов и MAXNUM = 3000 в течение разумного времени (в идеале не более 10 минут)

Редактировать: Вот мой код для практического использования в соответствии с просьбой:

import itertools
import sys
import time

sys.setrecursionlimit(10000000)

#["Name/Carbs/Protein/Fat/Vitamins/Calories"]
available = ['Fiddleheads/3/1/0/3/80', 'Fireweed Shoots/3/0/0/4/150', 'Prickly Pear Fruit/2/1/1/3/190', 'Huckleberries/2/0/0/6/80', 'Rice/7/1/0/0/90', 'Camas Bulb/1/2/5/0/120', 'Beans/1/4/3/0/120', 'Wheat/6/2/0/0/130', 'Crimini Mushrooms/3/3/1/1/200', 'Corn/5/2/0/1/230', 'Beet/3/1/1/3/230', 'Tomato/4/1/0/3/240', 'Raw Fish/0/3/7/0/200', 'Raw Meat/0/7/3/0/250', 'Tallow/0/0/8/0/200', 'Scrap Meat/0/5/5/0/50', 'Prepared Meat/0/4/6/0/600', 'Raw Roast/0/6/5/0/800', 'Raw Sausage/0/4/8/0/500', 'Raw Bacon/0/3/9/0/600', 'Prime Cut/0/9/4/0/600', 'Cereal Germ/5/0/7/3/20', 'Bean Paste/3/5/7/0/40', 'Flour/15/0/0/0/50', 'Sugar/15/0/0/0/50', 'Camas Paste/3/2/10/0/60', 'Cornmeal/9/3/3/0/60', 'Huckleberry Extract/0/0/0/15/60', 'Yeast/0/8/0/7/60', 'Oil/0/0/15/0/120', 'Infused Oil/0/0/12/3/120', 'Simple Syrup/12/0/3/0/400', 'Rice Sludge/10/1/0/2/450', 'Charred Beet/3/0/3/7/470', 'Camas Mash/1/2/9/1/500', 'Campfire Beans/1/9/3/0/500', 'Wilted Fiddleheads/4/1/0/8/500', 'Boiled Shoots/3/0/1/9/510', 'Charred Camas Bulb/2/3/7/1/510', 'Charred Tomato/8/1/0/4/510', 'Charred Corn/8/1/0/4/530', 'Charred Fish/0/9/4/0/550', 'Charred Meat/0/10/10/0/550', 'Wheat Porridge/10/4/0/10/510', 'Charred Sausage/0/11/15/0/500', 'Fried Tomatoes/12/3/9/2/560', 'Bannock/15/3/8/0/600', 'Fiddlehead Salad/6/6/0/14/970', 'Campfire Roast/0/16/12/0/1000', 'Campfire Stew/5/12/9/4/1200', 'Wild Stew/8/5/5/12/1200', 'Fruit Salad/8/2/2/10/900', 'Meat Stock/5/8/9/3/700', 'Vegetable Stock/11/1/2/11/700', 'Camas Bulb Bake/12/7/5/4/400', 'Flatbread/17/8/3/0/500', 'Huckleberry Muffin/10/5/4/11/450', 'Baked Meat/0/13/17/0/600', 'Baked Roast/4/13/8/7/900', 'Huckleberry Pie/9/5/4/16/1300', 'Meat Pie/7/11/11/5/1300', 'Basic Salad/13/6/6/13/800', 'Simmered Meat/6/18/13/5/900', 'Vegetable Medley/9/5/8/20/900', 'Vegetable Soup/12/4/7/19/1200', 'Crispy Bacon/0/18/26/0/600', 'Stuffed Turkey/9/16/12/7/1500']

global AllSP, AllNames
AllSP = []
AllNames = []

def findcombs(totalNames, totalCarbs, totalProtein, totalFat, totalVitamins, totalNutrients, totalCalories, MAXCALORIES):
    doneit = False
    for each in available:
        each = each.split("/")
        name = each[0]
        carbs = float(each[1])
        protein = float(each[2])
        fat = float(each[3])
        vitamins = float(each[4])
        nutrients = carbs+protein+fat+vitamins
        calories = float(each[5])
#        print(totalNames, totalCalories, calories, each)
        if sum(totalCalories)+calories <= MAXCALORIES:
            doneit = True
            totalNames2 = totalNames[::]
            totalCarbs2 = totalCarbs[::]
            totalProtein2 = totalProtein[::]
            totalFat2 = totalFat[::]
            totalVitamins2 = totalVitamins[::]
            totalCalories2 = totalCalories[::]
            totalNutrients2 = totalNutrients[::]

            totalNames2.append(name)
            totalCarbs2.append(carbs)
            totalProtein2.append(protein)
            totalFat2.append(fat)
            totalVitamins2.append(vitamins)
            totalCalories2.append(calories)
            totalNutrients2.append(nutrients)
#            print("    ", totalNames2, totalCarbs2, totalProtein2, totalFat2, totalVitamins2, totalNutrients2, totalCalories2)
            findcombs(totalNames2, totalCarbs2, totalProtein2, totalFat2, totalVitamins2, totalNutrients2, totalCalories2, MAXCALORIES)
        else:
            #find SP
            try:
                carbs    = sum([x * y for x, y in zip(totalCalories, totalCarbs)])    / sum(totalCalories)
                protein  = sum([x * y for x, y in zip(totalCalories, totalProtein)])  / sum(totalCalories)
                fat      = sum([x * y for x, y in zip(totalCalories, totalFat)])      / sum(totalCalories)
                vitamins = sum([x * y for x, y in zip(totalCalories, totalVitamins)]) / sum(totalCalories)
                balance  = (carbs+protein+fat+vitamins)/(2*max([carbs,protein,fat,vitamins]))
                thisSP   = sum([x * y for x, y in zip(totalCalories, totalNutrients)]) / sum(totalCalories) * balance + 12
            except:
                thisSP = 0
            #add SP and names to two lists
            AllSP.append(thisSP)
            AllNames.append(totalNames)

def main(MAXCALORIES):
    findcombs([], [], [], [], [], [], [], MAXCALORIES)
    index = AllSP.index(max(AllSP))
    print()
    print(AllSP[index], "  ", AllNames[index])

for i in range(100, 3000, 10):
    start = time.time()
    main(i)
    print("Calories:", i, ">>> Time:", time.time()-start)

Answer 1

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

foofInfo = [ food.split("/") for food in available ]
foofInfo = { food[0]:tuple([int(v) for v in food[1:]]) for food in available } #name:(carbs,proteins,fat,vitamins,nutrients,calories)

calFood = {}
for name,(_,_,_,_,calories) in foofInfo.items():
    if calories not in calFood: calFood[calories] = []
    calFood[calories].append(name)

maxCalories = 3000
for calories,foods in calFood.items():
    maxCount = maxCalories//calories
    print("Up to ",maxCount," of ",", ".join(foods))

Таким образом, вы можете предложитьпрогрессивное уточнение доступных опций, а не комбинация bazillion:

Up to  37  of  Fiddleheads, Huckleberries
Up to  20  of  Fireweed Shoots
Up to  15  of  Prickly Pear Fruit
Up to  33  of  Rice
Up to  25  of  Camas Bulb, Beans, Oil, Infused Oil
Up to  23  of  Wheat
Up to  15  of  Crimini Mushrooms, Raw Fish, Tallow
Up to  13  of  Corn, Beet
Up to  12  of  Tomato
Up to  12  of  Raw Meat
Up to  60  of  Scrap Meat, Flour, Sugar
Up to  5  of  Prepared Meat, Raw Bacon, Prime Cut, Bannock, Baked Meat, Crispy Bacon
Up to  3  of  Raw Roast, Basic Salad
Up to  6  of  Raw Sausage, Camas Mash, Campfire Beans, Wilted Fiddleheads, Charred Sausage, Flatbread
Up to  150  of  Cereal Germ
Up to  75  of  Bean Paste
Up to  50  of  Camas Paste, Cornmeal, Huckleberry Extract, Yeast
Up to  7  of  Simple Syrup, Camas Bulb Bake
Up to  6  of  Rice Sludge, Huckleberry Muffin
Up to  6  of  Charred Beet
Up to  5  of  Boiled Shoots, Charred Camas Bulb, Charred Tomato, Wheat Porridge
Up to  5  of  Charred Corn
Up to  5  of  Charred Fish, Charred Meat
Up to  5  of  Fried Tomatoes
Up to  3  of  Fiddlehead Salad
Up to  3  of  Campfire Roast
Up to  2  of  Campfire Stew, Wild Stew, Vegetable Soup
Up to  3  of  Fruit Salad, Baked Roast, Simmered Meat, Vegetable Medley
Up to  4  of  Meat Stock, Vegetable Stock
Up to  2  of  Huckleberry Pie, Meat Pie
Up to  2  of  Stuffed Turkey

Answer 2

Правильно, поэтому задача для N продуктов питания имеет временную и пространственную сложность O(exp(N)).Вам нужен какой-то эвристический поиск, например A * (ссылка) , который следует некоторому представлению о том, «насколько хороша» одна неполная комбинация, чтобы направлять ее дальнейший поиск.В результате вы найдете не лучшее решение, но практическое хорошее решение в течение ограниченного времени.Альтернативами являются генетические алгоритмы, имитация отжига и другие алгоритмы оптимизации.Обратите внимание, что вы должны определить показатель, насколько хороша каждая комбинация!

Я использовал пакет astar (https://github.com/jrialland/python-astar) в моем игровом AI, и он превзошел мои ожидания.

Дополнительные предложения: используйте namedtuple, чтобы сделать ваш код более читабельным, иначе вам не понравится находить ошибки и расширять их:

from collections import namedtuple

food = namedtuple('Food', 'name carbs protein fat vitamins calories')

bananas = food('bananas', 10, 15, 20, 10, 100)
oranges = food('oranges', carbs=10, protein=15, fat=20, vitamins=10, calories=100)
print(bananas.calories, oranges.fat)