笛卡尔乘积+ N×M的动态数组 [英] Cartesian Product + N x M Dynamic Array

问题描述

我已经看过小时没有任何成功的解决方案。希望有人能帮助我。

I have looked hours for a solution without any success. Hopefully someone can help me out.

我有N个M上原始邮政编码$ C CS动态数组。

I have a dynamic array of N items on M origin zip codes.

例如：

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

Item 1: 11001, 54010, 60621 Item 2: 11001, 60621 Item 3: 60621

我想创建一个新的数组，这将是这样的：

I want to create a new array that will look like this:

路线1：11001，11001，60621
路线2：11001，60621，60621
路线3：54010，11001，60621

Route 1: 11001, 11001, 60621 Route 2: 11001, 60621, 60621 Route 3: 54010, 11001, 60621

等等 - 直到6号线

建议？

----------------------有没有办法做到这一点没有使用LINQ？ VB.net和LINQ不要一起去：）

---------------------- Is there any way to accomplish this WITHOUT using Linq? VB.net and Linq do not go together :)

由于提前，

尼克

推荐答案

这听起来像你想从这个函数<一个href=\"http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx\">Eric利珀特的博客帖子书面回应生成所有可能的组合的：

It sounds like you want this function from Eric Lippert's blog post written in response to Generating all Possible Combinations:

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

这将让你写code是这样的：

That would let you write code like this:

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

和得到的输出是这样的：

And get output like this:

11001, 11001, 60621
11001, 60621, 60621
54010, 11001, 60621
54010, 60621, 60621
60621, 11001, 60621
60621, 60621, 60621

编辑：下面是VB.NET的版本（在VS2010）

Here's the VB.NET version (in 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完全递归实现：

Of course, if you don't want any LINQ whatsoever, here's a completely LINQ-free recursive implementation:

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少的方法：

It doesn't return the items in the same order as the first function, but is otherwise functionally identical. If you don't like LINQ or recursion, here's a single LINQ-less method that does the same thing as the recursive version:

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

这篇关于笛卡尔乘积+ N×M的动态数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！