生成一个n元笛卡尔积的示例

Question

我发现Eric Lippert在这里发表的文章与我遇到的问题非常契合。

我的问题是，对于两个或更多的集合，我不知道该如何使用它。

举例：

var collections = new List<List<MyType>>();
foreach(var item in somequery)
{
    collections.Add(
            new List<MyType> { new MyType { Id = 1} .. n }
        );
}

如何将笛卡尔积linq查询应用于“collections”变量？

该扩展方法如下：

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关于2个集合的示例：

var arr1 = new[] {"a", "b", "c"};
var arr2 = new[] { 3, 2, 4 };
var result = from cpLine in CartesianProduct(
                     from count in arr2 select Enumerable.Range(1, count)) 
             select cpLine.Zip(arr1, (x1, x2) => x2 + x1);

- Stefan Anghel

---

可能是[列表排列（未知数量）]的重复问题。 (https://dev59.com/AGrXa4cB1Zd3GeqPAprf) - Rawling

@EricLippert的扩展方法比那些可能的重复问题中的任何解决方案都更易理解（至少对我来说），而且更为简洁。 - Stefan Anghel

Answer 1

样例代码已经能够进行“n”个笛卡尔积（在示例中进行了3次）。您的问题是，您拥有一个List<List<MyType>>，而需要的是一个IEnumerable<IEnumerable<MyType>>。

IEnumerable<IEnumerable<MyType>> result = collections
  .Select(list => list.AsEnumerable())
  .CartesianProduct();

- Amy B

---

不需要使用AsEnumerable()，因为每个List已经是IEnumerable了，请参见：https://dev59.com/r2vXa4cB1Zd3GeqPJ4WM#46327167 - TermoTux

@Infinum 不完全正确... CartesianProduct 方法需要一个 IEnumerable<IEnumerable<T>>。如果你不调用 AsEnumerable，那么你会得到一个 IEnumerable<List<T>>，这是不兼容的。 - Amy B

Answer 2

与这个问题的原始发布者一样，我也很难理解这个强大函数的用法。主要困扰我的是，在调用函数之前，我必须创建一个充满IEnumerable的单一对象（与原帖一样）。

我的代码设置方式是有3个包含数据的数组需要相乘，创建这个更大的IEnumerable会增加额外的步骤，我不想这样做。

因此，我将函数重写为扩展自IEnumerable<T>而不是IEnumerable<IEnumerable<T>>，现在我可以直接从任何我想要相乘的数组中调用该函数，并将其他两个数组作为参数传递。如果其他人也想以这种方式使用它，我想重新发布这篇文章。

    public static IEnumerable<IEnumerable<T>> CartesianProduct<T>
    (this IEnumerable<T> firstSequence, params IEnumerable<T>[] sequences)
    {
        IEnumerable<IEnumerable<T>> result = new[] { Enumerable.Empty<T>() };

        foreach (IEnumerable<T> sequence in (new[] { firstSequence }).Concat(sequences))
        {
            result = from resultItem in result 
                     from sequenceItem in sequence 
                     select resultItem.Concat(new[] { sequenceItem });
        }
        return result;
    }

这是在三个数据数组上使用该方法的示例。

        var numbers = new object[] { 1, 2, 3 };
        var letters = new object[] { "a", "b", "c" };
        var colors = new object[] { "red", "blue", "yellow" };

        var result = numbers.CartesianProduct(letters, colors);

输出

        [1, a, red]
        [1, a, blue]
        [1, a, yellow]
        [1, b, red]
        [1, b, blue]
        [1, b, yellow]
        [1, c, red]
        [1, c, blue]
        [1, c, yellow]
        [2, a, red]
        [2, a, blue]
        [2, a, yellow]
        [2, b, red]
        [2, b, blue]
        [2, b, yellow]
        [2, c, red]
        [2, c, blue]
        [2, c, yellow]
        [3, a, red]
        [3, a, blue]
        [3, a, yellow]
        [3, b, red]
        [3, b, blue]
        [3, b, yellow]
        [3, c, red]
        [3, c, blue]
        [3, c, yellow]

- Blake

---

嗨，@Blake，当计算笛卡尔积时，处理大量集合中的项目时是否遇到了OutOfMemory异常？ - manishKungwani

Answer 3

由于 List<T> 是 IEnumerable<T>，因此使用 Eric 的解决方案解决您的问题如下：

var collections = new List<List<MyType>>();
var product =  collections.CartesianProduct();
foreach(var collection in product)
{
    // a single collection of MyType items
    foreach(var item in collection)
    {
        // each item of type MyType within a collection
        Console.Write(item);
    }    
}

当然，你可以更简洁地聚合每个集合中的项，例如作为单个字符串：

var product = 
    collections
    .CartesianProduct()
    .Select(xs => xs.Aggregate(new StringBuilder(), (sb, x) => sb.Append(x.ToString()), sb => sb.ToString()));

foreach(var collectionAsString in product)
{
    Console.WriteLine(collectionAsString);
}

- TermoTux