Cross product of arrays

[Robert Bravery]

Hi all,

Can some one show me how to achieve a cross product of arrays. So that if I
had two arrays (could be any number) with three elements in each (once again
could be any number) I would get:
the two arrays
{"one","two","three"},{"red","green","blue}
the result
one red
one green
one blue
two red
two green
two blue
three red
three green
three blue

Thanks

Robert

 

[Jon Skeet [C# MVP]]

Can some one show me how to achieve a cross product of arrays. So that if I
had two arrays (could be any number) with three elements in each (once again
could be any number) I would get:
the two arrays
{"one","two","three"},{"red","green","blue}
the result
one red
one green
one blue
two red
two green
two blue
three red
three green
three blue

What do you want to do with the cross product? Just printing it out is
easy:

using System;

public class Test
{
static void Main()
{
string[] first = {"one", "two", "three"};
string[] second = {"red", "green", "blue"};

foreach (string x in first)
{
foreach (string y in second)
{
Console.WriteLine ("{0} {1}", x, y);
}
}
}
}

 

[Robert Bravery]

WEll I want to eventual extract the data and save it to a table.
I used two arrays as an example, but infact I don't know how many array sets
there can be, up to a maximum of 5, so there could be any number from one
to five sets. Then each array set can have any number of elements in that
array
The point is I don't know how many sets there will be , to a mx of five, and
I don't know how many elements there will be in each set
so I could also have the following, I dont know:

{'apple','orange','banana'},{'man','woman','child'},{'red','green','blue','w
hite','black'}

which should produce a cross product like:

apple man red
apple man green
apple man blue
apple man white
apple man black
apple woman red
apple woman green
apple woman blue
apple woman white
apple woman black
apple child red
apple child green
apple child blue
apple child white
apple child black
orange man red
orange man green
orange man blue
orange man white
orange man black
orange woman red
orange woman green
orange woman blue
orange woman white
orange woman black
orange child red
orange child green
orange child blue
orange child white
orange child black
banana man red
banana man green
banana man blue
banana man white
banana man black
banana woman red
banana woman green
banana woman blue
banana woman white
banana woman black
banana child red
banana child green
banana child blue
banana child white
banana child black

Thanks
Robert

Can some one show me how to achieve a cross product of arrays. So that if I
had two arrays (could be any number) with three elements in each (once again
could be any number) I would get:
the two arrays
{"one","two","three"},{"red","green","blue}
the result
one red
one green
one blue
two red
two green
two blue
three red
three green
three blue

What do you want to do with the cross product? Just printing it out is
easy:

using System;

public class Test
{
static void Main()
{
string[] first = {"one", "two", "three"};
string[] second = {"red", "green", "blue"};

foreach (string x in first)
{
foreach (string y in second)
{
Console.WriteLine ("{0} {1}", x, y);
}
}
}
}

 

[Jon Skeet [C# MVP]]

WEll I want to eventual extract the data and save it to a table.
I used two arrays as an example, but infact I don't know how many array sets
there can be, up to a maximum of 5, so there could be any number from one
to five sets. Then each array set can have any number of elements in that
array
The point is I don't know how many sets there will be , to a mx of five, and
I don't know how many elements there will be in each set
so I could also have the following, I dont know:

{'apple','orange','banana'},{'man','woman','child'},{'red','green','blue','w
hite','black'}

which should produce a cross product like:

Okay. Here's a sample which takes as many string arrays as you like. It
uses recursion, which wouldn't be a good idea if you wanted a cross-
product of very deep arrays, but then that quickly becomes infeasible
anyway.

You'll want to consider how you want to process the table - you could
fairly easily write an iterator which returns a string array on each
iteration, especially with C# 2.0 iterators.

using System;
using System.Text;

public class Test
{
static void Main()
{
string[] first = {"one", "two", "three"};
string[] second = {"red", "green", "blue"};

PrintCrossProduct(new string[]{"apple","orange","banana"},
new string[]{"man","woman","child"},
new string[]{"red","green","blue",
"white","black"});
}

static void PrintCrossProduct(params string[][] arrays)
{
PrintCrossProduct(arrays, 0, new string[arrays.Length]);
}

static void PrintCrossProduct(string[][] arrays,
int depth, string[] current)
{
for (int i=0; i < arrays[depth].Length; i++)
{
current[depth] = arrays[depth];
if (depth < arrays.Length-1)
{
PrintCrossProduct(arrays, depth+1, current);
}
else
{
StringBuilder builder = new StringBuilder();
foreach (string x in current)
{
builder.Append(x);
builder.Append(" ");
}
// Remove the extraneous trailing space
// (This will fail if there are no arrays, but you can
// guard against that if you need to)
builder.Length--;
Console.WriteLine (builder);
}
}
}
}

 

[Lucian Wischik]

The point is I don't know how many sets there will be , to a mx of five, and
I don't know how many elements there will be in each set
so I could also have the following, I dont know:
{'apple','orange','banana'},{'man','woman','child'},{'red','green','blue','w
hite','black'}

To review here, each of these elements is an IEnumerable<string>.
Therefore the cross-product will be an
IEnumerable<IEnumerable<string>>. So here's the code:


static IEnumerable<string> pre(string x, IEnumerable<string> ys)
{ yield return x;
if (ys!=null) foreach (string y in ys) yield return y;
}

static IEnumerable<IEnumerable<string>>
cross(IEnumerable<string> xs, IEnumerable<IEnumerable<string>> yss)
{ foreach (string x in xs)
{ if (yss==null) yield return prepend(x,null);
else foreach(IEnumerable<string>ys in yss) yield return pre(x,ys);
}
}

static void Main(string[] args)
{ string[][] ars = new string[][] {new string[]{"a","b","c","d"},
new string[]{"u","v"},
new string[]{"x","y","z"}};

// Here we assemble the cross product of all of those strings:
IEnumerable<IEnumerable<string>> c = null;
foreach (string[] ar in ars) c=cross(ar,c);

// and let's print out the cross product!
foreach (IEnumerable<string> cs in c)
{ foreach (string s in cs) Console.Write(s+",");
Console.WriteLine();
}
}

 

[Lucian Wischik]

{ foreach (string x in xs)
{ if (yss==null) yield return prepend(x,null);
else foreach(IEnumerable<string>ys in yss) yield return pre(x,ys);
}

Sorry, that should have been "yield return pre(x,null)" in the second
line.


Note that this solution has no recursion! This code uses c# "yield
return" iterators. Internally these construct an object on the heap
whose job it is to keep track of the enumeration. Effectively, the
role played by recursive stack-frames in Jon's code is fulfilled here
by the yield-return objects.

 

[Robert Bravery]

Thanks,
A bit confusing at first. But actually works great

Robert