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

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)
                    return true;
                    walk[whoIncrement] = 0;
            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" }

            foreach (var item in cross.Get())
                Console.WriteLine("{0}\t{1}\t{2}", item[0], item[1], item[2]);
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

Send mail to the author(s) E-mail

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

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

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