Form a multidimensional cartesian product array

Question

I have a function that generates a cartesian product for me

        var abcArray = new string[] { "a", "b", "c" };
        var xyzArray = new string[] { "1", "2", "3" };

        var combos = CartesianProductSmart(abcArray, xyzArray);
    private static string[][] CartesianProductSmart(string[] arr1, string[] arr2)
    {
        return arr1.SelectMany(s1 => arr2, (s1, s2) => new string[] { s1, s2 })
            .ToArray();
    }

My output looks like:

a,1
a,2
a,3
b,1
b,2
b,3
c,1
c,2
c,3

How can I transform this function into something more complex, like forming multidimensional arrays:

array3 = [ {"A1", "B2", "C3"},
           {"A1", "B3", "C2"},
           {"A2", "B1", "C3"},
           {"A2", "B3", "C1"}, 
           {"A3", "B2", "C1"},
           {"A3", "B1", "C2"}
          ]

What I want is the cartesian product just using every element of both arrays and form that into an array. (I'm aware that the array sizes will differ based on inputs). My idea so far is to do the cartesian product, assign the first element as the first cartesian product result and then iterate over the rest of the cartesian products and add into a new array by checking if there's no duplicates, then selecting only unique members, but that seems highly inefficient.

Answer 1

My advise would be, if you are using complex structures, you should not use standard structures anymore, but create classes that represent the data that you model and the operations that you can perform on these objects.

Apparently your program has the notion of Matrix (not sure if you use the same term in English mathematics)

A Matrix of M by N has M columns, and N rows.

I'm not sure if it is wise to put your abcarray in a matrix of 3 by 1, or that you want to put that in a special class that you would call a Vector. Maybe a Vector is a derived class of matrix of N by 1? or 1 by N?

Anyway, apparently you can do an operation on two Vectors:

class Vector
{
    public Matrix<T> CartesianProduct(Vector<T> v)
    {
        return CartesianProduct(this, v);
    }
    public static Matrix<T> CartesianProduct(Vector<T> x, Vector<T> y) {...}

Usage would be:

Vector<string> x = new Vector<string>(new string[] { "a", "b", "c" });
Vector<string> y = new Vector<string>(new string[] { "1", "2", "3" });
Matrix<string> m = x.CartesianProduct(y);

Well this looks neat enough to me, so let's continue on this path.

A Vector has a Dimension. When creating a Vector object, you have to specify the Dimension. During lifetime of the Vector you can't change its Dimension.

A Vector has Coordinates, numbered from 0 to Dimension-1. You can get and set a specific Coordinate. For simplicity we use the index to access the Coordinates.

Operations that you can do on a Vector: Add / Subtract / Negate / Multiply / ... This is a bit out of scope of your question so I won't go in to this.

class Vector<T> : IReadonlyCollection<T>
{
    private readonly T[] coordinates;

    public Vector(int dimension)
    {
        // TODO: check dimension > 0;
        this.coordinates = new T[dimension];
    }
    public Vector(IEnumerable<T> data)
    {
        // TODO: check data != null; check data contains at least one element
        this.Coordinates = data.ToArray();
    }

    // TODO: other constructors? ICloneable?
    // TODO: Add / Subtract / Multiply with a number?
    public T this[int index] 
    {
        get => this.coordinates[index];
        set => this.coordinates[index] = value;
    }
}

Implementation of IReadOnlyCollection is fairly straightforward:

public int Count => this.coordinates.Length;
public Enumerator<T> GetEnumerator()
{
    return this.Coordinates.GetEnumerator();
}
IEnumerator Enumerable.GetEnumerator()
{
    return this.GetEnumerator();
}

For initializations the following extension methods would be nice. If you are not familiar with extension methods, read extension methods demystified

public static Vector<T> AsVector<T>(IEnumerable<T> source)
{
    return new Vector<T>(source.ToArray());
}

Usage:

var abcArray = new string[] { "a", "b", "c" };
var abcVector = abcArray.AsVector();

I design a Matrix as a non-changeable two dimensional array.

class Matrix<T>
{
    private readonly T[,] elements;

    public Matrix(int columnCount, int rowCount)
    {
        this.elements = new T[columnCount, rowCount];
    }

    public Matrix(T[,] elements)
    {
        this.elements = elements;
    }

    public int RolumnCount => this.elements.GetLength[0];
    public int RowCount => this.elements.GetLength[1];

    // etc, invent several other useful operations on matrices.
    // addition, multiplication, linear transformation, ...
}

Of course, if you really want to interpret a Matrix as a two dimensional array:

public T[,] Elements => this.elements

Finally the cartesian product of two vectors, returning a Matrix. The problem is, that we need a function to "combine" one x-coordinate with one "y" coordinate. With a vector of numbers this could be a multiplication, with a vector of strings you want to use concatenation.

public static Matrix<T> CartesianProduct(Vector<T> vectorX, Vector<T> vectorY, 
    Func<T, T, T> combine)
{
    // TODO: input not null; correct dimension

    IEnumerable<T> combinations = vectorX.SelectMany(vectorY,
     (xCoordinate, yCoordinate) => combine(xCoordinate, yCoordinate);

    return new Matrix<T>(combinations);
}

Vector<string> abcArray = new Vector<string>(new string[] { "a", "b", "c" });
Vector<string> xyzArray = new Vector<string>(new string[] { "1", "2", "3" });
Matrix<string> m = Vector.CartesianProduct(abcArray, xyzArray, (x, y) => x + y);

Answer 2

Using an extension method to generate permutations with Heap's algorithm based on swapping in an array (from this Stackoverflow answer), you can compute the permutations of the ["1", "2", "3"] array and merge them with the ["a", "b", "c"] array using LINQ.

Here is the extension method for permutations:

public static class IEnumerableExt {
    /// <summary>
    /// From StackOverflow answer https://stackoverflow.com/a/36634935/2557128
    /// EO: 2016-04-14
    /// Generator of all permutations of an array of anything.
    /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
    /// Heap's algorithm to find all permutations. Non recursive, more efficient.
    /// </summary>
    /// <param name="items">Items to permute in each possible ways</param>
    /// <param name="funcExecuteAndTellIfShouldStop"></param>
    /// <returns>Return true if cancelled</returns>
    public static IEnumerable<T[]> Permutations<T>(this IEnumerable<T> itemsSrc) {
        T[] items;
        if (itemsSrc is T[] arrayOfItems)
            items = arrayOfItems;
        else
            items = itemsSrc.ToArray();

        /// <summary>
        /// Swap 2 elements of same type
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="a"></param>
        /// <param name="b"></param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void Swap(ref T a, ref T b) {
            T temp = a;
            a = b;
            b = temp;
        }

        int countOfItem = items.Length;
        yield return items;
        if (countOfItem <= 1)
            yield break;

        var indexes = new int[countOfItem];
        for (int i = 1; i < countOfItem;) {
            if (indexes[i] < i) {
                if ((i & 1) == 1) // test if i odd: if (i % 2 == 1)  ... more efficient ??? At least the same.
                    Swap(ref items[i], ref items[indexes[i]]);
                else
                    Swap(ref items[i], ref items[0]);

                yield return items;

                indexes[i]++;
                i = 1;
            }
            else
                indexes[i++] = 0;
        }
    }
}

Now you can just:

var ans1 = xyzArray.Permutations().Select(p => abcArray.Zip(p, (x,a) => x+a));

If you prefer an array of arrays, you can add that to LINQ:

var ans2 = xyzArray.Permutations().Select(p => abcArray.Zip(p, (x,a) => x+a).ToArray()).ToArray();