The official Fatica Labs Blog! RSS 2.0
# Friday, August 12, 2011

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 A1, ..., An be n sets.

Then the set of all ordered n-tuples <x1, ..., xn> , where xi Ai for all i, 1 i n ,

is called the Cartesian product of A1, ..., An, and is denoted by A1 ... An .

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:

 

image

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.
Friday, August 12, 2011 11:46:46 AM (GMT Daylight Time, UTC+01:00)  #    Comments [1] - Trackback
Programmin | Recipes

My Stack Overflow
Contacts

Send mail to the author(s) E-mail

Tags
profile for Felice Pollano at Stack Overflow, Q&A for professional and enthusiast programmers
About the author/Disclaimer

Disclaimer
The opinions expressed herein are my own personal opinions and do not represent my employer's view in any way.

© Copyright 2014
Felice Pollano
Sign In
Statistics
Total Posts: 157
This Year: 0
This Month: 0
This Week: 0
Comments: 123
This blog visits
All Content © 2014, Felice Pollano
DasBlog theme 'Business' created by Christoph De Baene (delarou) and modified by Felice Pollano