Find possible variations of one item

Question

In my application, I have the notion of recipes and each recipe has ingredients which can be replaced by another ingredient. What I want to do is to generate every possibility with each ingredients. I have the following structure as CLR objects:

public class Food
{
    public Food()
    {
        NutritionalValues = new Collection<FoodNutritionalValue>();
    }

    public string Name { get; set; }
    public string Category { get; set; }

    public ICollection<FoodNutritionalValue> NutritionalValues { get; set; }
}

public class FoodNutritionalValue
{
    public string Type { get; set; }
    public decimal Value { get; set; }
}

public class Recipe
{
    public Recipe()
    {
        IngredientGroups = new Collection<IngredientGroup>();
    }

    public string Name { get; set; }
    public ICollection<IngredientGroup> IngredientGroups { get; set; }
}

public class IngredientGroup
{
    public IngredientGroup()
    {
        Ingredients = new Collection<Food>();
    }

    public ICollection<Food> Ingredients { get; set; }
}

IngredientGroup is something that can be replaced each other. So, for a recipe, there needs to be one ingredient from each of the IngredientGroups. However, as I don't know the IngredientGroups count, I'm unable to iterate through them to find out each possibility.

For example, the following code works fine if I were to know the count of the IngredientGroups.Count beforehand

Recipe recipe2 = new Recipe();
IngredientGroup ingredientGroup3 = new IngredientGroup();
IngredientGroup ingredientGroup4 = new IngredientGroup();
IngredientGroup ingredientGroup5 = new IngredientGroup();

recipe2.Name = "Recipe2";
ingredientGroup3.Ingredients.Add(new Food { Name = "Food8", Category = "Categor8" });
ingredientGroup3.Ingredients.Add(new Food { Name = "Food9", Category = "Categor9" });

ingredientGroup4.Ingredients.Add(new Food { Name = "Food5", Category = "Categor5" });
ingredientGroup4.Ingredients.Add(new Food { Name = "Food10", Category = "Categor10" });
ingredientGroup4.Ingredients.Add(new Food { Name = "Food11", Category = "Category11" });

ingredientGroup5.Ingredients.Add(new Food { Name = "Food3", Category = "Categor3" });
ingredientGroup5.Ingredients.Add(new Food { Name = "Food4", Category = "Categor4" });

recipe2.IngredientGroups.Add(ingredientGroup3);
recipe2.IngredientGroups.Add(ingredientGroup4);
recipe2.IngredientGroups.Add(ingredientGroup5);

var recipes = new[] { recipe2 };

List<string> results = new List<string>();
foreach (var rcp in recipes)
{
    var group1 = rcp.IngredientGroups.ElementAt(0);
    var group2 = rcp.IngredientGroups.ElementAt(1);
    var group3 = rcp.IngredientGroups.ElementAt(2);

    foreach (var item1 in group1.Ingredients)
        foreach (var item2 in group2.Ingredients)
            foreach (var item3 in group3.Ingredients)
            {
                results.Add(string.Format("{0}, {1}, {2}", item1.Name, item2.Name, item3.Name));
            }
}

I'm sure I am missing something too big here. Anybody knows how I can generate the every possibility on runtime?

Answer 1

Based on the answer found Here, you could probably use the same helper methods:

public static List<List<T>> CombinationsOf<T>(List<List<T>> sets)
{    
  var combinations = new List<List<T>>();

  foreach (var value in sets[0])
    combinations.Add(new List<T> { value });

  foreach (var set in sets.Skip(1))
    combinations = AddSet(combinations, set);

  return combinations;
}

private static List<List<T>> AddSet<T>(List<List<T>> combinations, List<T> set)
{
  var result = from value in set
               from combination in combinations
               select new List<T>(combination) { value };

  return result.ToList();
}

Usage Example (based on OP's example)

...
var foods = recipes.SelectMany(recipe => 
  recipe.IngredientGroups.Select(ingredient =>
    ingredient.Ingredients.Select(o => o.Name).ToList()));

var results = from combination in CombinationsOf(foods.ToList())
              select string.Join(", ", combination);
...

Output

results :=

Food8, Food5, Food3 
Food9, Food5, Food3 
Food8, Food10, Food3 
Food9, Food10, Food3 
Food8, Food11, Food3 
Food9, Food11, Food3 
Food8, Food5, Food4 
Food9, Food5, Food4 
Food8, Food10, Food4 
Food9, Food10, Food4 
Food8, Food11, Food4 
Food9, Food11, Food4