有没有一种好的LINQ方法来进行笛卡尔积？

Question

我有一个类结构，像这样：

Person
Dogs (dog 1, dog 2, etc)
Puppies (puppy A, puppy B, etc)

有一个人，他有1到n只狗。每只狗都有1到n只小狗。

我想要一个包含所有可能组合的小狗列表，每只狗选一只小狗。例如：

狗1的小狗A，狗2的小狗A 狗1的小狗A，狗2的小狗B 狗1的小狗B，狗2的小狗A 狗1的小狗B，狗2的小狗B

如果是在SQL表中，我会像以下这样去“乘法”连接这些表：

select * from puppies a, puppies b where a.parent='dog1' and b.parent='dog2'

有没有一种类似于linq的方法来做这种事情？

非常感谢。

- Chris

Answer 1

如果我理解正确，您想要n组小狗的笛卡尔积。

如果您在编译时知道有几组集合，那么很容易获得笛卡尔积：

from p1 in dog1.Puppies
from p2 in dog2.Puppies
from p3 in dog3.Puppies
select new {p1, p2, p3};

假设狗1有小狗p11、p12，狗2有小狗p21，狗3有小狗p31、p32。这样你就得到了：

{p11, p21, p31},
{p11, p21, p32},
{p12, p21, p31},
{p12, p21, p32}

每行都是一个匿名类型。如果您在编译时不知道有多少组，请做更多的工作来处理它。请参阅我的这篇文章：

http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

以及这个StackOverflow问题：

Generating all Possible Combinations

一旦您拥有了CartesianProduct<T>方法，那么您可以这样说：

CartesianProduct(from dog in person.Dogs select dog.Puppies)

获取

{p11, p21, p31},
{p11, p21, p32},
{p12, p21, p31},
{p12, p21, p32}

每一行都是一系列小狗。

听起来合理吗？

- Eric Lippert

---

那么我说这是递归编程的替代方案，是正确的吗？ - The Muffin Man

@Nick：我认为更恰当的说法是这是一种替代命令式编程的方法。LINQ 的重点在于你说出你想要什么——你以声明式的方式编程——然后编译器根据可用的运行时库来确定如何实现它。如果这些库使用递归编程或迭代编程来完成工作，那就是它们的事情了。 - Eric Lippert

这很有道理，然而在我所问的这个问题中（https://dev59.com/nlXTa4cB1Zd3GeqP0lZ8），我无法想出如何使用LINQ获得结果而不使用递归编程，是否有更短的方法？ - The Muffin Man

@Nick：当然有解决办法。据我理解，你的问题可以很容易地通过非递归方法解决。我会发布一个答案。 - Eric Lippert

Answer 2

dogs.Join(puppies, () => true, () => true, (one, two) => new Tuple(one, two));

您可以执行普通的 join 操作，但是选择器都会返回相同的值，因为我希望所有组合都是有效的。在组合时，请将它们同时放入一个元组（或其他您选择的数据结构）中。

leftSide.SelectMany((l) => rightSide, (l, r) => new Tuple(l, r));

这应该会执行笛卡尔积。

- McKay

---

这是很多问题。(1) SelectMany的重点不是将多个IEnumerable<T>折叠成一个IEnumerable<T>吗？是的，尽管它的功能当然不止于此。从“序列”的角度来看，SelectMany是具有投影的笛卡尔积运算符。从更一般的“单子”角度来看，SelectMany是单子模式下的绑定操作。 - Eric Lippert

“我找不到一种将查询推导笛卡尔积翻译成流畅语法的方法。”- 我建议你参考C# 4.0规范书的第7.16.2.4节，其中详细说明了如何进行这种翻译。 - Eric Lippert

“join”不是被定义为笛卡尔积的一组有限集合吗？ 是的，逻辑上，“join”确实是笛卡尔积上的一个过滤器。但是，在实现时并非如此。 “Join”被优化用于等值连接的情况；在LINQ to Objects实现中，会在后台积极构建哈希表，以便对结果集远小于它过滤的笛卡尔积的情况下高效地实现“join”相等语义。如果您想要的是笛卡尔积，则不要使用一个设计用于过滤笛卡尔积的昂贵设备;只需生成产品即可！ - Eric Lippert

（4）我是否缺少运算符？据我所知，不是。 - Eric Lippert

“from”子句只等同于“foreach”子句，还是有单独的运算符？我不知道这个问题的意思。根本不存在“foreach”子句，而且当你说“等价关系”时，我也不知道你描述的是哪些集合。你能澄清一下这个问题吗？ - Eric Lippert

Answer 3

如果你想获得狗和小狗的所有可能组合，你需要执行一个交叉连接(cross join)：

from dog in Dogs
from puppy in Puppies
select new
{
    Dog = dog,
    Puppy = puppy
}

- Anders Fjeldstad

---

我实际上想要N组小狗的所有可能组合，但感谢您让我走上了正确的轨道。 - Chris

Answer 4

    string[] colors = { "Red", "Green", "Blue" };
    string[] sizes = { "Small", "Medium", "Large" };
    
    var result = from color in colors
                 from size in sizes
                 select new { Color = color, Size = size };
    
    foreach (var item in result)
    {
        Console.WriteLine(item);
    }

- Software Sith Lord

Answer 5

我喜欢麦凯的想法，完整的示例如下所示。

var r = new Random();
var d = Enumerable.Range(1, 3).ToDictionary(x => Guid.NewGuid(), y => Enumerable.Range(1, 10).Select(z => r.Next()).ToList());
var kvps = d.Keys.SelectMany((key) => d[key], (key, value) => new KeyValuePair<Guid, int>(key, value));
var l = kvps.ToLookup(kvp => kvp.Key, kvp => kvp.Value);

- Dawid Ireno

---

在我看来，这只是给一个简洁明了的方法增加了很多噪音。 - Gert Arnold