Декартовой продукт + динамический массив N x M

Question

Я смотрел часы для решения без каких-либо успехов. Надеюсь, кто-то может мне помочь.

У меня есть динамический массив из N элементов в почтовых индексах M origin.

Например:

Пункт 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 не идут вместе :)

Answer 1

То, что вы хотите сделать, - это сгенерировать комбинации каждого элемента в массиве.

Вот пример жестко закодированы для 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 случаев.

Answer 2

Вы можете использовать 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 }; 

Answer 3

Это звучит, как вы хотите, чтобы эта функция от Eric Lippert's blog post написано в ответ на 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}));     
} 

Это позволит вам писать код так:

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 

EDIT: Вот версия 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; 
}