I have a list of recipes and a list of ingredients.

Each recipe is defined by one or more set(s) of ingredients.

This means that some recipes have more than 1 way of being accomplished.

A simple example:

recipe1 = (("egg", "salt", "pepper"))
recipe2 = (("egg", "carrot", "ham"), ("cream", "carrot", "ham"))
recipes = (recipe1, recipe2)

I want to simplify recipes by deleting some set of ingredients.

• I want only one set per recipe
• I want the list of unique_ingredients to be as small as possible

If I delete ("egg", "carrot", "ham") from recipe2, recipes will become (("egg", "salt", "pepper"),("cream", "carrot", "ham")), which has 6 unique elements ("egg", "salt", "pepper", "cream", "carrot", "ham")

While if I delete ("cream", "carrot", "ham") from recipe2, recipes will become (("egg", "salt", "pepper"),("egg", "carrot", "ham")), which has 5 unique elements ("egg", "salt", "pepper", "carrot", "ham")

How would you proceed to delete the set of elements while minimizing the number of unique elements?

CodePudding user response：

Check through the cartesian product of ingredients (it.product) and pick the combination with the fewest items (min over len(set(...))).

recipe1 = (("egg", "salt", "pepper"), )
recipe2 = (("egg", "carrot", "ham1"), ("cream", "carrot", "ham"))
recipes = (recipe1, recipe2)


import itertools as it

recipe_and_sizes = [(len(set(it.chain(*x))), x) for x in it.product(*recipes)]
recipes = min(recipe_and_sizes)[1]
print(recipes)

(('egg', 'salt', 'pepper'), ('egg', 'carrot', 'ham1'))
>