使用LINQ实现列表集合的笛卡尔积的两种方法

Question

使用LINQ实现列表集合的笛卡尔积的两种方法

c#linqgenericscartesian-product

6

我需要创建一组列表的笛卡尔积。例如，我有：

{ {4,3,7}, {1,2,9}, {5,8} }

我需要得到： {4,1,5}, {4,1,8}, {3,1,5}, {3,1,8}, ... , {7,9,8}

目前我已经学习到，可以使用类似以下代码来实现：

var lists = new List<List<int>>
{ 
    new List<int> { 4, 3, 7},
    new List<int> { 1, 2, 9},
    new List<int> { 5, 8},
};

IEnumerable<IEnumerable<int>> empty = new[] { Enumerable.Empty<int>() };
var agg = lists.Aggregate(
    empty,
    (acc, next) 
=>  
    (from ac in acc
    from n in next
    select ac.Concat(new[] {n})));

然而，最初我实现它的方法如下：

var lists = new List<List<int>>
{ 
    new List<int> { 4, 3, 7},
    new List<int> { 1, 2, 9},
    new List<int> { 5, 8},
};

var agg = lists.Aggregate(
    new List<List<int>>() {new List<int> {}},
    (acc, next) 
=>  
    (from ac in acc
    from n in next
    select ac.Add(n)).ToList());

这个具体实现无法编译，出现以下错误：

在查询表达式中，不允许使用类型为“System.Collections.Generic.List”的表达式作为后续 from 子句的源类型，“System.Collections.Generic.List>” 中的调用“SelectMany”类型推断失败。

我对这个错误信息有点困惑。我看不出为什么在那个位置上不允许使用 List？

- Farhad Alizadeh Noori

2

请查看Eric Lippert关于此主题的博客文章：http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx - DavidG

你是否事先知道会有多少个列表，还是列表数量为N？ - terrybozzio

@DavidG 谢谢你的 Linq。我已经阅读了那篇文章，我认为那就是我记得要使用 Aggregate 的原因。我的问题不是如何执行笛卡尔积，而是关于上面提到的错误。 - Farhad Alizadeh Noori

@terrybozzio 这是任意数量的项目（N个项目）。 - Farhad Alizadeh Noori

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cyanfish · Accepted Answer

错误信息的第一部分有些误导性。以下代码可以成功编译和运行：

var agg = lists.Aggregate(
    new List<List<int>>(),
    (acc, next) 
=>  
    (from ac in acc
    from n in next
    // select ac.Add(n)).ToList());
    select ac.Concat(new[] {n}).ToList()).ToList());

真正的问题在于 select ac.Add(n)。一个 select 子句必须返回一个值（在本例中是一个 List<int>），但你调用的 List<T>.Add 修改了原始列表并返回 void。

在内部，LINQ 试图将此 LINQ 表达式转换为（除其他外）对 Enumerable.SelectMany 的调用。编译器传递的参数之一是生成的 lambda 表达式，它返回 ac.Add(n)（即 void）。编译器尝试根据 SelectMany 可用的重载推断生成的 lambda 的类型，但没有兼容的重载，因此无法确定 lambda 的类型。因此出现了“在调用 'SelectMany' 时类型推断失败”的错误消息。

与 Add 一样，大多数 List<T> 方法通常不适用于 LINQ 的函数式编程，这就是为什么首选解决方案仅依赖于 IEnumerable<T> 及其与 LINQ 相关的扩展方法的原因。