这个问题在这里已经有了答案:
9年前关闭。
Possible Duplicate:
Generating all Possible Combinations
Is there a good LINQ way to do a cartesian product?
How to generate combination of N elements with limited supply of 2 each without explicit nested loops
我有一个列表列表,我想迭代所有可能的组合,从每个内部列表中选择一个元素。如果我在编译时知道有多少个列表,这非常简单,但是如果我事先不知道会有多少个列表,我该怎么做呢?
如果我有三个列表(并且如果我知道在编译时将恰好有三个列表),并且我想要从三个列表中的每一个中选择一个元素的所有组合,我可以使用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[][]
我在上面的示例输出中显示。)
最佳答案
您不使用 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 的所有答案一样,他包括一个 detailed discussion就等效的非 LINQ 代码而言,它确切地说明了这是如何以及为什么起作用的。
关于combinations - 使用 LINQ 迭代组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7924585/