笛卡尔积 + N x M 动态数组

Question

笛卡尔积 + N x M 动态数组

c#arrayscartesian-product

6

我已经花了数小时寻找解决方案，但都没有成功。希望有人能够帮助我。

我有一个包含N个项目在M个起始邮政编码的动态数组。

例如：

项目1：11001、54010、60621 项目2：11001、60621 项目3：60621

我想创建一个新的数组，它将如下所示：

路径1：11001、11001、60621 路径2：11001、60621、60621 路径3：54010、11001、60621

等等 - 直到第6条路线。

有什么建议吗？

---------------------- 有没有不使用Linq就能完成这个任务的方法？VB.net和Linq不配合 :)

- Nick Warren

1

我不理解你生成路由的逻辑...那么这些“items”到底代表什么呢？请提供更多关于你尝试做什么的细节！ - Thomas Levesque

可能是生成所有可能组合的重复问题。 - Gabe

你将它标记为C#，你需要VB解决方案吗？ - Gabe

我现在发布了一个LINQ版本，一个递归版本和一个循环版本。还有什么问题吗？ - Gabe

3个回答

4

你可以使用linq来实现这个功能：

var item1 = new[] { 11001, 54010, 60621 };
var item2 = new[] {  11001, 60621 };
var item3 = new [] { 60621 };
IEnumerable<int[]> cartesian = 
    from i1 in item1
    from i2 in item2
    from i3 in item3
    select new[] { i1, i2, i3 };

- m0sa

0

你要做的是生成数组中每个项目的组合。

以下是N == 3 的硬编码示例：

        var array1 = new[] { 1101, 5410, 60621 };
        var array2 = new[] { 1101, 60621 };
        var array3 = new[] { 60621 };

        foreach (var a in array1)
        {
            foreach (var b in array2)
            {
                foreach (var c in array3)
                {
                    Console.WriteLine("{0},{1},{2}", a, b, c);
                }
            }
        }

看看你能否将其适应于N个案例。

- OJ.

我想我将不得不使用 Gabe 的答案。 - Nick Warren

你如何将其适应于N个案例？ - Nick Warren

Nick Warren：将此解决方案调整为N种情况需要使用递归或一些复杂的循环和栈。请参阅我的编辑答案，了解两者的示例。 - Gabe

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

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

- Gabe · Accepted Answer

听起来你想要这个函数，它来自Eric Lippert的博客文章，是为了回应生成所有可能组合而编写的：

public 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}));                
}

那将使您编写以下代码：

这样做：

int[][] items = { 
                    new[] { 11001, 54010, 60621 },
                    new[] { 11001, 60621 },
                    new[] { 60621 }
                };
var routes = CartesianProduct(items);
foreach (var route in routes)
    Console.WriteLine(string.Join(", ", route));

并获得以下输出：

11001、11001、60621
11001、60621、60621
54010、11001、60621
54010、60621、60621
60621、11001、60621
60621、60621、60621

编辑：这是VB.NET版本（在VS2010中）

Imports System.Runtime.CompilerServices

Module Module1
    <Extension()>
    Private Function CartesianProduct(Of T)(
            ByVal sequences As IEnumerable(Of IEnumerable(Of T))) _
            As IEnumerable(Of IEnumerable(Of T))
        Dim emptyProduct As IEnumerable(Of IEnumerable(Of T)) =
            New IEnumerable(Of T)() {Enumerable.Empty(Of T)()}
        Return sequences.Aggregate(
            emptyProduct,
            Function(accumulator, sequence)
                Return (From accseq In accumulator
                        From item In sequence
                        Select accseq.Concat(New T() {item}))
            End Function)
    End Function

    Sub Main(ByVal args As String())
        Dim items = New Integer()() {New Integer() {11001, 54010, 60621},
                                     New Integer() {11001, 60621},
                                     New Integer() {60621}}
        Dim routes = items.CartesianProduct()
        Dim route As IEnumerable(Of Integer)
        For Each route In routes
            Console.WriteLine(String.Join(", ", route))
        Next
    End Sub
End Module

当然，如果您不想使用任何LINQ，这里有一个完全不含LINQ的递归实现：

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    this IEnumerable<IEnumerable<T>> sequences)
{
    var accum = new List<T[]>();
    var list = sequences.ToList();
    if (list.Count > 0)
        CartesianRecurse(accum, new Stack<T>(), list, list.Count - 1);
    return accum;
}

static void CartesianRecurse<T>(List<T[]> accum, Stack<T> stack,
                                List<IEnumerable<T>> list, int index)
{
    foreach (T item in list[index])
    {
        stack.Push(item);
        if (index == 0)
            accum.Add(stack.ToArray());
        else
            CartesianRecurse(accum, stack, list, index - 1);
        stack.Pop();
    }
}

它不会按照第一个函数返回项目的相同顺序，但在功能上是相同的。如果你不喜欢LINQ 或者递归，这里有一个单一的不使用LINQ的方法，可以执行与递归版本相同的操作：

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    this IEnumerable<IEnumerable<T>> sequences)
{
    var accum = new List<T[]>();
    var list = sequences.ToList();
    if (list.Count > 0)
    {
        var enumStack = new Stack<IEnumerator<T>>();
        var itemStack = new Stack<T>();
        int index = list.Count - 1;
        var enumerator = list[index].GetEnumerator();
        while (true)
            if (enumerator.MoveNext())
            {
                itemStack.Push(enumerator.Current);
                if (index == 0)
                {
                    accum.Add(itemStack.ToArray());
                    itemStack.Pop();
                }
                else
                {
                    enumStack.Push(enumerator);
                    enumerator = list[--index].GetEnumerator();
                }
            }
            else
            {
                if (++index == list.Count)
                    break;
                itemStack.Pop();
                enumerator = enumStack.Pop();
            }
    }
    return accum;
}