使用LINQ迭代组合

Question

可能重复:
生成所有可能的组合
是否有一个很好的LINQ方式来做笛卡尔积？
如何在没有显式嵌套循环的情况下生成N个元素的组合,每个元素的供应量为2

我有一个列表列表,我想迭代所有可能的组合,我从每个内部列表中选择一个元素.如果我在编译时知道有多少列表,这是非常简单的,但是如果我事先不知道会有多少列表,我怎么能这样做呢？

如果我有三个列表(如果我知道,在编译时,将会有三个列表),并且我想要从三个列表中的每个列表中选择一个元素的所有组合,我可以轻松地使用LINQ查询:

var list1 = new[] { 1, 2 };
var list2 = new[] { 3, 4 };
var list3 = new[] { 5, 6 };
var combinations = from item1 in list1
                   from item2 in list2
                   from item3 in list3
                   select new[] { item1, item2, item3 };
// Results:
// {1, 3, 5}
// {1, 3, 6}
// {1, 4, 5}
// {1, 4, 6}
// {2, 3, 5}
// {2, 3, 6}
// {2, 4, 5}
// {2, 4, 6}

但是,当我在编译时不知道会有多少列表时,我怎么能做同样的事情呢？

var lists = new[] {
    new[] { 1, 2 },
    new[] { 3, 4 },
    new[] { 5, 6 } };
var combinations = ???;

// This particular example happens to be the same inputs as above, so it
// has the same expected outputs. But there could be two lists instead,
// or four, so the three hard-coded "from" clauses won't work.

看起来这应该在LINQ中实际可行 - SelectMany已经相当于两个嵌套的foreach循环,所以我需要做的就是做一堆SelectMany调用然后将所有结果与另一个SelectMany结合起来.或者其他的东西.但是当它开始变得那样的时候,我的大脑就会被打结.我无法理解如何将各个部分组合在一起.我甚至无法弄清楚外部SelectMany调用的泛型类型参数是什么.

如何迭代这些列表列表,并返回所有组合,而不知道在编译时会有多少列表？

(注意:无论我在上面使用过IEnumerable<T>哪些数组,我都可以使用代替.在示例代码中,数组更容易编写,但我希望输出更可能是在表单IEnumerable<IEnumerable<int>>而不是int[][]我在我的表单中显示以上样本输出.)

Answer 1

您不使用 SelectMany 来组合 SelectMany 调用；你使用聚合。代码由Eric Lippert提供（回答了一个比这个问题更具体的问题，但给出了一个也适合这个问题的一般答案）：

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 accseq in accumulator 
            from item in sequence 
            select accseq.Concat(new[] {item}) :                         
        );
}

与 Eric 的所有答案一样，他包含了详细的讨论，根据等效的非 LINQ 代码准确地阐述了其工作方式和原因。