Cartesian products + dynamic array N x M

Question

I looked at the watch for a solution without any success. Hope someone can help me.

I have a dynamic array of N elements in M ​​origin zip codes.

For instance:

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

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

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

etc. - to route 6.

Suggestions?

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

Answer 1

It looks like you need this feature from the Eric Lippert blog post written in response to Creating 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})); } 

This will allow you to 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 we get the following conclusion:

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

EDIT: here is the version of VB.NET (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 

Of course, if you do not need any LINQ, here is a complete recursive implementation without 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(); } } 

It does not return elements in the same order as the first function, but is otherwise functionally identical. If you don't like LINQ or recursion, here's one 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; } 

Answer 2

You can use linq to do this:

 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

What you want to do is generate combinations of each element in the array.

Here's an example hardcoded for 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); } } } 

See if you can adapt this for N cases.