Sometimes happens that we need to roll over all the combinations of elements in multiple arrays. This operation is called Cartesian Product and is defined as:
Definition (Cartesian product): Let A_{1}, ..., A_{n} be n sets.
Then the set of all ordered n-tuples <x_{1}, ..., x_{n}> , where x_{i} A_{i} for all i, 1 i n ,
is called the Cartesian product of A_{1}, ..., A_{n}, and is denoted by A_{1} ... A_{n} .
Achieving this is possible by some linq tricks, or by an helper class I propose in this post. But just for clarify let’s start from the example:
We have three array as below:
{ "JUICY", "SWEET" }
{ "GREEN", "YELLOW" }
{ "APPLE", "BANANA", "MANGO" }
we want to obtain all the possible tuples, ie:
This can be achieved by the following code ( helper class ):
public class CartesianProduct<T>
{
int[] lengths;
T[][] arrays;
public CartesianProduct(params T[][] arrays)
{
lengths = arrays.Select(k => k.Length).ToArray();
if (lengths.Any(l => l == 0))
throw new ArgumentException("Zero lenght array unhandled.");
this.arrays = arrays;
}
public IEnumerable<T[]> Get()
{
int[] walk = new int[arrays.Length];
int x = 0;
yield return walk.Select(k => arrays[x++][k]).ToArray();
while (Next(walk))
{
x = 0;
yield return walk.Select(k => arrays[x++][k]).ToArray();
}
}
private bool Next(int[] walk)
{
int whoIncrement = 0;
while (whoIncrement < walk.Length)
{
if (walk[whoIncrement] < lengths[whoIncrement] - 1)
{
walk[whoIncrement]++;
return true;
}
else
{
walk[whoIncrement] = 0;
whoIncrement++;
}
}
return false;
}
}
And, just for completeness, the example application:
static void Main(string[] args)
{
var cross = new CartesianProduct<string>(
new string[] { "JUICY", "SWEET" }
, new string[] { "GREEN", "YELLOW" }
, new string[] { "APPLE", "BANANA", "MANGO" }
);
Console.WriteLine("=========================================================");
foreach (var item in cross.Get())
{
Console.WriteLine("{0}\t{1}\t{2}", item[0], item[1], item[2]);
}
Console.WriteLine("=========================================================");
}
Really simple and clear to use in comparison with other linq based solution, even when arrays are unknown at design time.