使用LINQ迭代组合

Question

我有一个列表的列表，我想迭代所有可能的组合，其中我从每个内部列表中选择一个元素。如果我在编译时知道有多少个列表，那么这就很简单了，但是如果我不知道将会有多少个列表，我该怎么做呢？

如果我有三个列表（如果我在编译时知道将恰好有三个列表），并且我想要从这三个列表中选择单个元素的所有组合，那么我可以通过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[][]。）

- Joe White

---

这是你的答案。 - Ufuk Hacıoğulları

这不是那两个“问题”的重复——两个问题都在询问固定数量的列表，但两个问题实际上都包含了一个变量数量列表情况下的答案（同一人在两种情况下给出的答案！）。 - Joe White

@Steven，你链接的问题比我的更新，所以如果有什么问题，它就是这个问题的副本。 - Joe White

Answer 1

你不使用 SelectMany 来组合 SelectMany 调用，而是使用 Aggregate。这段代码由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代码如何以及为什么起作用，以等效的非LINQ代码形式。

- Joe White