Calculating n-ary Cartesian Product

Question

The method gets called extensively throughout my programm, is there any way I can speed it up or improve other aspects?

---

The code calculates the n-ary Cartesian Product of a List containing n Lists, so that for example:

Product([[1],[2,3],[4,5]]) yields [1,2,4],[1,2,5],[1,3,4],[1,3,5]

public static IEnumerable<T[]> Product<T>(T[][] items)
    {
        T[] currentItem = new T[items.Length];
        static IEnumerable<T[]> go(T[][] items, T[] currentItem, int index)
        {
            if (index == items.Length)
            {
                yield return currentItem;
                yield break;
            }
            else
            {
                foreach (T item in items[index])
                {
                    currentItem[index] = item;
                    foreach(var j in go(items, currentItem, index + 1))
                    {
                        yield return j;
                    }
                }
            }

        }
        return go(items, currentItem, 0);
    }

---

A possible problem i can think of, is the

foreach(var j in go(items, currentItem, index + 1))
       {
           yield return j;
       }

section, since it takes n yields for every (single) array that is part of the n-ary Cartesian Product.

Answer 1

The implementation contains one small but important bug (or feature?), it yields the same array instance from each loop.

Consider this example.

int[][] numbers = new[] { new[] { 1 }, new[] { 2, 3 }, new[] { 4, 5 } };

foreach (int[] arr in Product(numbers))
{
    Console.WriteLine(string.Join(", ", arr));
}

The output is perfect

1, 2, 4
1, 2, 5
1, 3, 4
1, 3, 5

But if you want to store the result as jagged array and process it later:

foreach (int[] arr in Product(numbers).ToArray())
{
    Console.WriteLine(string.Join(", ", arr));
}

You'll get this output

1, 3, 5
1, 3, 5
1, 3, 5
1, 3, 5

That's because it's an array of four references to the same array.

Next small thing is one redundant line of code

yield break;

You don't need it because previous line is the last statement in the method. The method exits after it.

Fix is simple

public static IEnumerable<T[]> Product<T>(T[][] items)
{
    T[] currentItem = new T[items.Length];
    static IEnumerable<T[]> Go(T[][] items, T[] currentItem, int index)
    {
        if (index == items.Length)
        {
            yield return (T[])currentItem.Clone();
        }
        else
        {
            foreach (T item in items[index])
            {
                currentItem[index] = item;
                foreach (T[] j in Go(items, currentItem, index + 1))
                {
                    yield return (T[])j.Clone();
                }
            }
        }
    }
    return Go(items, currentItem, 0);
}

That's it.

Performance while keeping it as returning arrays will be slow because e.g. for 10 arrays of 10 items it will yield 10*10*10*10*10*10*10*10*10*10 = 10000000000 arrays of 10 items each. But you want up to 15. It won't be fast at all.

But let's try to eliminate the recursion.

Consider an alternative implementation of the same

public static IEnumerable<T[]> MyProduct<T>(T[][] items)
{
    int length = items.Length;
    int[] indexes = new int[length];

    while (true)
    {
        T[] arr = new T[length];
        for (int i = 0; i < length; i++)
        {
            arr[i] = items[i][indexes[i]];
        }
        yield return arr;

        int row = length - 1;
        indexes[row]++;
        while (indexes[row] == items[row].Length)
        {
            if (row == 0)
                yield break;
            indexes[row] = 0;
            row--;
            indexes[row]++;
        }
    }
}

To understand this implementation imagine a digital clock. What if you make 3 arrays 24,60,60 items and fill it with numbers from 0 to 23/59. The Product will yield time to display for each second of the day - 86400 arrays of 3 items each. Then imagine how clock counts time on display and you'll catch the idea of this implementation.

Looks like it works

1, 2, 4
1, 2, 5
1, 3, 4
1, 3, 5

And finally let's make a benchmark for both implementations. Using Benchmark.NET of course. For example with 6 arrays of 6 items each.

[MemoryDiagnoser]
public class MyBenckmark
{
    private int[][] numbers;

    [GlobalSetup]
    public void Setup()
    {
        numbers = new int[6][];
        for (int i = 0; i < 6; i++)
        {
            numbers[i] = Enumerable.Range(i * 6, 6).ToArray();
        }
    }

    [Benchmark]
    public void RunProduct()
    {
        foreach(var _ in Product(numbers)) ;
    }

    [Benchmark]
    public void RunMyProduct()
    {
        foreach (var _ in MyProduct(numbers)) ;
    }


    public static IEnumerable<T[]> Product<T>(T[][] items)
    {
        T[] currentItem = new T[items.Length];
        static IEnumerable<T[]> Go(T[][] items, T[] currentItem, int index)
        {
            if (index == items.Length)
            {
                yield return (T[])currentItem.Clone();
            }
            else
            {
                foreach (T item in items[index])
                {
                    currentItem[index] = item;
                    foreach (T[] j in Go(items, currentItem, index + 1))
                    {
                        yield return (T[])j.Clone();
                    }
                }
            }
        }
        return Go(items, currentItem, 0);
    }

    public static IEnumerable<T[]> MyProduct<T>(T[][] items)
    {
        int length = items.Length;
        int[] indexes = new int[length];

        while (true)
        {
            T[] arr = new T[length];
            for (int i = 0; i < length; i++)
            {
                arr[i] = items[i][indexes[i]];
            }
            yield return arr;

            int row = length - 1;
            indexes[row]++;
            while (indexes[row] == items[row].Length)
            {
                if (row == 0)
                    yield break;
                indexes[row] = 0;
                row--;
                indexes[row]++;
            }
        }
    }
}

Go!

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19042
Intel Core i7-4700HQ CPU 2.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=5.0.102
  [Host]     : .NET Core 3.1.11 (CoreCLR 4.700.20.56602, CoreFX 4.700.20.56604), X64 RyuJIT
  DefaultJob : .NET Core 3.1.11 (CoreCLR 4.700.20.56602, CoreFX 4.700.20.56604), X64 RyuJIT

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
RunProduct	28.509 ms	0.2488 ms	0.2077 ms	6750.0000	-	-	20.08 MB
RunMyProduct	1.274 ms	0.0103 ms	0.0086 ms	712.8906	-	-	2.14 MB

You vote.