LINQ交叉连接列表列表？未知数量列表的笛卡尔积

Question

假设我有以下 class - ItemMenu - 以及列表列表。如何使用 C# 生成包含所有可用组合的交叉联接输出？

对于以下代码，我希望得到 3（温度）乘以 4（侧面）乘以 4（饮料）的结果，例如：

稀有牛排，没有配菜，没有饮料
没有边的稀有牛排和啤酒
没有配菜的稀有牛排和葡萄酒
没有边的稀有牛排和可乐
稀有牛排配沙拉，不含饮料
...（共48种组合）

显然，事先不知道修饰符和修饰符选项的数量，所以如果我们有 4 个修饰符，每个修饰符有 5 个选项，我们最终会得到 5*6*6*6（第一个是强制性的，其余的添加了 none 选项）结果。我正在考虑使用 LINQ SelectMany 展平列表，但我无法通过未知数量的选项产生预期结果。我正在考虑将所有选项记录为数组中的位标志并进行计数，但存在这个强制标志问题。

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" },
                }
            }
        }
    };
}

至于输出类型，我最好使用 ItemMenu 对象列表并将 ModifierOptions 标志设置为 true，但任何类型的输出对象都是可以接受的，甚至是字符串。谢谢！

Answer 1

尝试以下操作：

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; }
    }

}

Answer 2

回答标题中的问题，使用 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}))));
}

据我了解，您想像这样使用它：

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

编辑：将累加器更改为使用 Enumerable.Empty<T>() 而不是实例化数组，因为它避免了分配。

Answer 3

感谢 Rosetta Code 我找到了一个简洁的扩展方法：

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 }));
}

上述方法接受列表的列表并生成所有组合：

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();
}

不幸的是，这没有考虑 IsRequired 标志，但仍然呈现所有组合

LINQ交叉连接列表列表？未知数量列表的笛卡尔积

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

c#

linq

cross-join