Cartesian product of an array with itself a variable amount of times?

Question

I want to write a function which returns the cartesian product of an array with itself a variable amount of times.

Now, if the number of cartesian products is known at compile time, then I can do the following (for 3 cartesian products):

public static void Main(string[] args)
        {
            int[] numSet = {1,2,3,4};
                        
            var cartesianProduct = from letter in numSet
                                   from number in numSet
                                   from colour in numSet
                                   select new { num1, num2, num3};
        }

Now, I have seen this answer: https://stackoverflow.com/a/4073806/5859885, which seems to provide a method for dealing with a variable amount of sets. The method is as follows:

static IEnumerable<IEnumerable<T>> CartesianProduct<T>(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 }));
        }

Now, I've applied this to my problem as follows (this is for 4 cartesian products (see the for loop), but can easily be wrapped in a method for a variable amount of cartesian products))

static void Main(string[] args)
        {

            int[] numSet= new int[] { 1, 2, 3, 4};
            List<int[]> numList = new List<int[]>();
            for(int i=0; i<4; i++)
            {
                numList.Add(numSet);
            }

            IEnumerable<IEnumerable<int>> combArray = CartesianProduct(numList);
            foreach(var combo in combArray)
            {
                Console.WriteLine(combo);
            }

        }

Now, this compiles, but I just get the following output for each iteration of the for loop (instead of the cartesian product). System.Linq.Enumerable+ConcatNIterator'1[System.Int32].

What is happening here?

Change write statement : Console.WriteLine(string.Join(",",combo)); — jdweng, Oct 24 '20 at 09:47
Thanks! Do you know how I can store each combination inside an array and then store all of these combos inside a single array? So I have a jagged array (array of arrays)? — the man, Oct 24 '20 at 09:58
They are already in the variable numList. It is not jagged, just a regular two dimensional array since the width is always 4. — jdweng, Oct 24 '20 at 12:35

score 1 · Answer 1 · answered Oct 26 '20 at 20:12

Modify the method to return each combination as an array:

static IEnumerable<T[]> CartesianProduct<T>(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 }).ToArray());
}

Then convert the final return into an array of arrays:

var combArray = CartesianProduct(numList).ToArray();

NOTE: In general, it is more efficient to use a List<int> instead of an int[] when building dynamically, also depending on how you are processing the answer, the IEnumerable<IEnumerable<int>> may be a better form, or the IEnumerable<int[]> rather than an array of arrays.

Cartesian product of an array with itself a variable amount of times?

1 Answers1