Produit cartésien + N x M Dynamic Array

Question

J'ai cherché des heures pour trouver une solution sans succès. J'espère que quelqu'un pourra m'aider. J'ai un tableau dynamique de N éléments sur les codes postaux d'origine M.

Par exemple:

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

Je veux créer un nouveau tableau qui ressemblera à ceci:

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

etc - jusqu'à ce que la route 6.

Suggestions?

---------------------- Existe-t-il un moyen d'accomplir ceci sans utiliser Linq? VB.net et Linq ne vont pas ensemble :)

Answer 1

Ce que vous cherchez à faire est de générer des combinaisons de chaque élément de la matrice.

Voici un exemple codé en dur pour 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); 
       } 
      } 
     } 

Voyez si vous pouvez adapter pour que N cas.

Answer 2

Vous pouvez utiliser LINQ pour que:

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

On dirait que vous voulez que cette fonction de Eric Lippert's blog post écrite en réponse à 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}));     
} 

qui vous permettent d'écrire du code comme ceci:

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

Et obtenir une sortie comme ceci:

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

EDIT: Voici la version VB.NET (en 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 

Bien sûr, si vous ne voulez pas que ce soit LINQ, voici une implémentation récursive complètement LINQ sans:

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

Il ne retourne pas les éléments dans le même ordre que la première fonction, mais est autrement identique sur le plan fonctionnel. Si vous ne l'aimez pas LINQ ou récursion, voici une méthode unique LINQ moins qui fait la même chose que la version récursive:

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