LINQ cross join list of lists? Cartesian product for unknown number of lists

Question

Let's presume I have the following class - ItemMenu - with a list of lists. How can I generate a cross join output with all of the combinations available, using C#?

For the following code I would expect 3 (temperature) times 4 (side) times 4 (drinks) results, eg:

Rare Steak with no side and no drink
Rare Steak with no side and Beer
Rare Steak with no side and Wine
Rare Steak with no side and Coke
Rare Steak with salad and no drink
... (total of 48 combinations)

Obviously, the amount of modifiers and modifiers options is not known in advance, so if we have 4 modifiers with 5 options each, we would end up with 5*6*6*6 (first is mandatory, the rest have none option added) results. I was thinking of flattening the lists with LINQ SelectMany but I could not produce expected result with unknown number of options. I'm considering recording all of the options as bit flags in an array and just counting up, but there's this mandatory flag issue.

public class ItemMenu
{
    public string Name { get; set; }
    public List<Modifier> Modifiers { get; set; }
}
public class Modifier
{
    public bool IsMandatory { get; set; }
    public string Name { get; set; }
    public List<ModifierOption> Options { get; set; }
}
public class ModifierOption
{
    public int ID { get; set; }
    public string Name { get; set; }
    public bool Selected { get; set; }
}
public static ItemMenu GetSteakMenu()
{
    return new ItemMenu
    {
        Name = "Beef Steak",
        Modifiers = new List<Modifier> {
            new Modifier {  Name = "Temperature", IsMandatory = true, Options = new List<ModifierOption>
                {
                    new ModifierOption { ID = 1, Name = "Rare" },
                    new ModifierOption { ID = 2, Name = "Medium" },
                    new ModifierOption { ID = 3, Name = "Well done" },
                }
            },
            new Modifier {  Name = "Side", Options = new List<ModifierOption>
                {
                    new ModifierOption { ID = 1, Name = "Salad" },
                    new ModifierOption { ID = 2, Name = "Fries" },
                    new ModifierOption { ID = 3, Name = "Sweet fries" },
                }
            },
            new Modifier {  Name = "Drink", Options = new List<ModifierOption>
                {
                    new ModifierOption { ID = 1, Name = "Beer" },
                    new ModifierOption { ID = 2, Name = "Wine" },
                    new ModifierOption { ID = 3, Name = "Coke" },
                }
            }
        }
    };
}

As of output type, preferably I would use list of ItemMenu objects with ModifierOptions flags set as true, but any type of output object is acceptable, even string. Thank you!

FYI this operation is usually called the *Cartesian product*; if you do a search you'll find many questions on this over the last decade. I've closed the question as a duplicate of one of them. — Eric Lippert, Oct 07 '19 at 20:15
Eric I'm aware of both. As you've might have seen, I'm aware of the name, hence I've used it in the question. Almost all answers used 2 arrays as an example, but I've needed unknown number of lists (and not arrays) — komsky, Oct 10 '19 at 11:30

V0ldek · Accepted Answer · 2019-10-07T17:40:23.583

Answering the question in the title, a product of an unknown number of lists using LINQ:

public static class EnumerableExtensions
{
    public static IEnumerable<IEnumerable<T>> CrossProduct<T>(
        this IEnumerable<IEnumerable<T>> source) => 
        source.Aggregate(
            (IEnumerable<IEnumerable<T>>) new[] { Enumerable.Empty<T>() },
            (acc, src) => src.SelectMany(x => acc.Select(a => a.Concat(new[] {x}))));
}

As far as I understand you want to use it like this:

var beefSteak = GetSteakMenu();
var modifiers = beefSteak.Modifiers.Select(m => m.Options);
var results = modifiers.CrossProduct();

foreach (var resultList in results)
{
    Console.WriteLine($"Steak, {string.Join(", ", resultList.Select(r => r.Name))}");
}

> Steak, Rare, Salad, Beer
> Steak, Medium, Salad, Beer
> Steak, Well done, Salad, Beer
> Steak, Rare, Fries, Beer
> Steak, Medium, Fries, Beer
> Steak, Well done, Fries, Beer
> Steak, Rare, Sweet fries, Beer
> Steak, Medium, Sweet fries, Beer
> Steak, Well done, Sweet fries, Beer
> Steak, Rare, Salad, Wine
> Steak, Medium, Salad, Wine
> Steak, Well done, Salad, Wine
> Steak, Rare, Fries, Wine
> Steak, Medium, Fries, Wine
> Steak, Well done, Fries, Wine
> Steak, Rare, Sweet fries, Wine
> Steak, Medium, Sweet fries, Wine
> Steak, Well done, Sweet fries, Wine
> Steak, Rare, Salad, Coke
> Steak, Medium, Salad, Coke
> Steak, Well done, Salad, Coke
> Steak, Rare, Fries, Coke
> Steak, Medium, Fries, Coke
> Steak, Well done, Fries, Coke
> Steak, Rare, Sweet fries, Coke
> Steak, Medium, Sweet fries, Coke
> Steak, Well done, Sweet fries, Coke

EDIT: Changed the accumulator to use Enumerable.Empty<T>() instead of instantiating an array, as it avoids an allocation.

score 1 · Answer 2 · answered Oct 07 '19 at 17:35

Thanks to the Rosetta Code I have found a neat extension method:

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) =>
        from acc in accumulator
        from item in sequence
        select acc.Concat(new[] { item }));
}

The above method accepts a list of lists and produces all combinations:

private static void Main(string[] args)
{
    ItemMenu steak = GetSteakMenu();
    var modArray = steak.Modifiers.ToArray();
    var combinations = steak.Modifiers.Select(mo => mo.Options).CartesianProduct();

    Console.WriteLine($"Total of {combinations.Count()}");
    foreach (var variation in combinations)
    {
        var array = variation.ToArray();
        for (int i = 0; i < array.Length; i++)
        {
            Console.WriteLine($"Modifier: {modArray[i].Name}, Option: {array[i]}");
        }
    }

    Console.WriteLine("Done!");
    Console.ReadKey();
}

Unfortunately, this does not consider the IsRequired flag, but still renders all combinations

Yeah, that's basically the same code I hacked together just before you posted it. The use of `Enumerable.Empty()` looks like it could be more efficient, though! — V0ldek, Oct 07 '19 at 17:37
Agree, V0ldek, that's why your answer is accepted. there's obviously place for improvement, but for now, it will do. — komsky, Oct 07 '19 at 17:39

jdweng · Answer 3 · 2019-10-07T18:48:24.790

Try following :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication135
{
    class Program
    {
        static ItemMenu menu = null;
        static List<List<ModifierOption>> modifiers = new List<List<ModifierOption>>();
        static void Main(string[] args)
        {
            menu = GetSteakMenu();
            GetRecursive(0, null);
        }
        static void GetRecursive(int level, List<ModifierOption> all)
        {
            foreach (ModifierOption option in menu.Modifiers[level].Options)
            {
                List<ModifierOption> newList = new List<ModifierOption>();
                if(all != null) newList.AddRange(all);
                newList.Add(option);
                if (level == menu.Modifiers.Count - 1)
                {
                    modifiers.Add(newList);
                }
                else
                {
                    GetRecursive(level + 1, newList);
                }
            }
        }

        public static ItemMenu GetSteakMenu()
        { 
            return new ItemMenu
            {
                Name = "Beef Steak",
                Modifiers = new List<Modifier> {
                    new Modifier {  Name = "Temperature", IsMandatory = true, Options = new List<ModifierOption>
                        {
                            new ModifierOption { ID = 1, Name = "Rare" },
                            new ModifierOption { ID = 2, Name = "Medium" },
                            new ModifierOption { ID = 3, Name = "Well done" },
                        }
                    },
                    new Modifier {  Name = "Side", Options = new List<ModifierOption>
                        {
                            new ModifierOption { ID = 1, Name = "Salad" },
                            new ModifierOption { ID = 2, Name = "Fries" },
                            new ModifierOption { ID = 3, Name = "Sweet fries" },
                        }
                    },
                    new Modifier {  Name = "Drink", Options = new List<ModifierOption>
                        {
                            new ModifierOption { ID = 1, Name = "Beer" },
                            new ModifierOption { ID = 2, Name = "Wine" },
                            new ModifierOption { ID = 3, Name = "Coke" },
                        }
                    }
                }
            };
        }

    }
    public class ItemMenu
    {
        public string Name { get; set; }
        public List<Modifier> Modifiers { get; set; }
    }
    public class Modifier
    {
        public bool IsMandatory { get; set; }
        public string Name { get; set; }
        public List<ModifierOption> Options { get; set; }
    }
    public class ModifierOption
    {
        public int ID { get; set; }
        public string Name { get; set; }
        public bool Selected { get; set; }
    }

}

Thank you for your answer, but this produces only 3 entries, and I would expect a minimum of 27 would all be mandatory. — komsky, Oct 07 '19 at 17:23

LINQ cross join list of lists? Cartesian product for unknown number of lists

3 Answers3