Generate all combinations of array of arrays

Question

I am unsing c#..

I have an araay of arrays, can grow to 30.

char[][] myArray = new char[][]{
 
        new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' },
    new char[] { '3', '2', '1' }
};

Want to create all combinations in format

"3333333333333333 3333333333333332 3333333333333331 3333333333333323 3333333333333322 3333333333333321 3333333333333313 3333333333333312 3333333333333311 3333333333333233 3333333333333232 ..........."

I applied two approaches, First:

var data=myArray.Aggregate((IEnumerable<string>)new[] { string.Empty }, (e, d) => e.SelectMany(_ => d, (a, b) => a + b)).ToList();
File.AppendAllText(@$"C:\test.txt", (String.Join(Environment.NewLine,data)));

In this appraoch, can generate sequences pretty quick as long as array count is 16. Above 16, I run into memory issue.

Second approach is

var positions = from list1 in mainList
                from list2 in mainList
                from list3 in mainList
                from list4 in mainList
......
 select new
 {
     list1,
     list2,
     list3,
....

Then use Parallel for loop using 32 threads. In second appraich, after running over 24 hours the loop is still running.

Is there another way to to do this faster wihtout running into memory issues...

Answer 1

You basically have 1, 2 and 3 as possible values. So they very much look like digits of a number. Let's create an initial array to have the state stored somewhere:

char[] myArray = new char[]{
 
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
    '1',
};

and let's create an array of values:

char[] values = new char[] {'1', '2', '3'};

Now, let's do a loop:

bool ended = false;
while (!ended) {
    bool done = false;
    int index = myArray.Length - 1;
    while ((!done) && (index >= 0)) {
        int valueIndex = values.IndexOf(myArray[index]);
        valueIndex = (valueIndex + 1) % values.Length;
        if ((valueIndex == 0) && (index == 0)) {
            ended = true;
            done = true;
        } else {
            myArray[index] = values[valueIndex];
            if (valueIndex == 0) {
                index--;
            } else {
                done = true;
                //output current state in the way you like
            }
        }
    }
}

We are basically "incrementing" a 3-base number where the array elements represent the digits.

EDIT

Concerns were expressed regarding IndexOf in the comment section. This is an implementation without IndexOf:

bool ended = false;
while (!ended) {
    bool done = false;
    int index = myArray.Length - 1;
    while ((!done) && (index >= 0)) {
        int valueIndex = myArray[index];
        valueIndex = (valueIndex + 1) % values.Length;
        if ((valueIndex == 0) && (index == 0)) {
            ended = true;
            done = true;
        } else {
            if (valueIndex == 0) {
                index--;
            } else {
                done = true;
                //output current state in the way you like
                //keep in mind that we will need to print
                //values[myArray[someindex]] in this scenario
            }
        }
    }
}

But, if we choose this approach, we will need to store the indexes in myArray rather than the actual values to be able to compute things based on them without IndexOf and hence we need to keep this in mind when we display the values too.

Answer 2

Unless I'm mistaken, this will do pretty much the same thing (conceptually):

char[][] myArray = new char[][]{
    new char[] { 'a', 'b', 'c' },
    new char[] { 'd', 'e', 'f' },
    new char[] { 'g', 'h', 'i' },
    new char[] { 'j', 'k', 'l' },
};
var digits = myArray.Length;
var numBase = myArray[0].Length;

for (int number = 0; number < Math.Pow(numBase, digits); number++)
{
    var str = new char[digits];
    var nNumber = number;
    for(int j = 0; j < digits; j++) {
        str[j] = myArray[j][nNumber % numBase];
        nNumber /= numBase;
    }
    Console.WriteLine(str);
}

Answer 3

I suspect that this could be an XY problem. And you don't actually "need" an array of arrays, but this is your idea how to solve your mysterious original problem. I simply added an assumption that you will only iterate over this array of arrays. If that's true than C# has a great feature called enumerators.

This is a very short code that during compilation will be expanded into a dedicated class that implements IEnumerator interface. During enumeration it will yield return array of chars one by one without actually allocating the memory for the entire array.

IEnumerable<char[]> GenerateArrays(string digits, int length)
{
    var characters = new char[length];

    var combinations = Math.Pow(digits.Length, length);

    for (var i = 0L; i < combinations; i++)
    {
        var temp = i;

        for (var j = 0; j < length; j++)
        {
            characters[length - 1 - j] = digits[(int)(temp % digits.Length)];
            temp /= digits.Length;
        }

        yield return characters;
    }
}


foreach (var array in GenerateArrays("321", 30))
{
    Console.WriteLine(array);
}

executing that code returns:

(...)
333333333333333333133223121221
333333333333333333133223121213
333333333333333333133223121212
333333333333333333133223121211
333333333333333333133223121133
333333333333333333133223121132
333333333333333333133223121131
333333333333333333133223121123
333333333333333333133223121122
333333333333333333133223121121
333333333333333333133223121113
333333333333333333133223121112
333333333333333333133223121111
(...)