Words with combination of letters from a given set in C#

Question

I'm trying to create a method that can output words where each letter can be any letter from a given set. For example:

First letter can be: A or B
Second letter can be AB or C
Third letter can be ABC or D
Fourth letter can be AB or C

and so on. I would store the input data as 2 dimensional array such as this:

AB
ABC
ABCD
ABC
ABC

And it should be able to generate words like:

AAAAA
BAAAA
ABAAA
etc.

And method would be called with a multidimensional array like this:

void printAllCombinations(int[,] arr)
{
    // Method code.
}

and I want to be able to call this method with a multidimensional array of any length and height. I have tried using for loops, but having too many for loops within each other is not the best solution.

Something I have tried:

private static List<string> combinations(string[][] twoDimStringArray)
        {
            // keep track of the size of each inner String array
            int[] sizeArray = new int[twoDimStringArray.Length];

            // keep track of the index of each inner String array which will be used
            // to make the next combination
            int[] counterArray = new int[twoDimStringArray.Length];

            // Discover the size of each inner array and populate sizeArray.
            // Also calculate the total number of combinations possible using the
            // inner String array sizes.
            int totalCombinationCount = 1;
            for (int i = 0; i < twoDimStringArray.Length; ++i)
            {
                sizeArray[i] = twoDimStringArray[i].Length;
                totalCombinationCount *= twoDimStringArray[i].Length;
            }

            // Store the combinations in a List of String objects
            List<String> combinationList = new List<string>(totalCombinationCount);

            StringBuilder sb;  // more efficient than String for concatenation

            for (int countdown = totalCombinationCount; countdown > 0; --countdown)
            {
                // Run through the inner arrays, grabbing the member from the index
                // specified by the counterArray for each inner array, and build a
                // combination string.
                sb = new StringBuilder();
                for (int i = 0; i < twoDimStringArray.Length; ++i)
                {
                    sb.Append(twoDimStringArray[i][counterArray[i]]);
                }
                combinationList.Add(sb.ToString());  // add new combination to list

                // Now we need to increment the counterArray so that the next
                // combination is taken on the next iteration of this loop.
                for (int incIndex = twoDimStringArray.Length - 1; incIndex >= 0; --incIndex)
                {
                    if (counterArray[incIndex] + 1 < sizeArray[incIndex])
                    {
                        ++counterArray[incIndex];
                        // None of the indices of higher significance need to be
                        // incremented, so jump out of this for loop at this point.
                        break;
                    }
                    // The index at this position is at its max value, so zero it
                    // and continue this loop to increment the index which is more
                    // significant than this one.
                    counterArray[incIndex] = 0;
                }
            }
            return combinationList;
        }

What would be an efficient way to go about this?

Answer 1

You need to find a cartesian product of all char lists. As mentioned in a comment, this has O(N^M) complexity where N = letters in each set, M = set count. Needless to say, computational time very quickly goes through the roof.

I wrote a generic extension method, which uses a recursive iterator method with yield return. It can be used to find a full cartesian product of any data types, not just char. I'm interested if this can be de-recursed.

Implementation:

public static class MultiCartesianExtension
{
    public static IEnumerable<TInput[]> MultiCartesian<TInput>(this IEnumerable<IEnumerable<TInput>> input)
    {
        return input.MultiCartesian(x => x);
    }

    public static IEnumerable<TOutput> MultiCartesian<TInput, TOutput>(this IEnumerable<IEnumerable<TInput>> input, Func<TInput[], TOutput> selector)
    {
        var inputList = input.ToList();
        var buffer = new TInput[inputList.Count];
        var results = MultiCartesianInner(inputList, buffer, 0);
        var transformed = results.Select(selector);
        return transformed;
    }

    private static IEnumerable<TInput[]> MultiCartesianInner<TInput>(IList<IEnumerable<TInput>> input, TInput[] buffer, int depth)
    {
        foreach (var current in input[depth])
        {
            buffer[depth] = current;
            if (depth == buffer.Length - 1)
            {
                var bufferCopy = (TInput[])buffer.Clone();
                yield return bufferCopy;
            }
            else
            {
                foreach (var a in MultiCartesianInner(input, buffer, depth + 1))
                {
                    yield return a;
                }
            }
        }
    }

Usage:

var input = new string[]
{
    "AB",
    "123",
    "@#",
};

foreach (var result in input.MultiCartesian(x => new string(x)))
{
    Console.WriteLine(result);
}

// Results:
// A1@
// A1#
// A2@
// A2#
// A3@
// A3#
// B1@
// B1#
// B2@
// B2#
// B3@
// B3#

For your particular case, this can be made more efficient by not creating a bufferCopy, and returning buffer itself. I did this to ensure usage safety for generic use. This is because to function correctly, buffer needs to be unmodified from the outside.