Dynamic nested loops to generate all possible combinations of array elements in c#

Question

I've searched stackoverflow and the web for similar questions, but i couldn't found the solution that i need.

I'm programming a code-list-generator.

so for example i have a List of chars like List<char> { 'a', 'b', 'c' };.

and i have a couple of settings like (int)minLength of 2 and a (int)maxLength of 3.

and i want this output :

aa
ab
ac
ba
bb
bc
ca
cb
cc

aaa
aab
aac
aba
abb
abc
aca
acb
acc

baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc

caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc

in gereral i would just kreate multidimensional loops, but i have to do this dynamically because of the diferent minLength, maxLength & charList values.

so i was going with a "self-calling-function" like this example:

    private void loop() {
        for( int i = 0; i < num; i++ ) {
            // stuff
            loop();
        }
    }

so far i've made following bunch of code, but in this stage i get stuck... :

    Thread mainThread;

    List<char> azlower;
    List<char> azupper;
    List<char> nullnine;

    List<char> totalChars;

    int totalNum;

    int levelCounter;

    bool running;

    public Form1() {
        InitializeComponent();
    }

    private void init() {
        azlower = new List<char> { 'a', 'b', 'c' , 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
        azupper = new List<char> { 'A', 'B', 'C' , 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
        nullnine = new List<char> { '0', '1', '2' /* , '3', '4', '5', '6', '7', '8', '9' */ };

        totalChars = new List<char> ();

        running = false;
    }

    private void button1_Click( object sender, EventArgs e ) {
        if( !running ) {
            init();

            // Start
            if( checkBoxAZ1.Checked ) {
                foreach( char character in azlower ) {
                    totalChars.Add( character );
                }
            }
            if( checkBoxAZ2.Checked ) {
                foreach( char character in azupper ) {
                    totalChars.Add( character );
                }
            }
            if( checkBox09.Checked ) {
                foreach( char character in nullnine ) {
                    totalChars.Add( character );
                }
            }
            if( checkBoxS.Checked && textBoxSpec.Text != "" ) {
                char[] specArray = textBoxSpec.Text.ToCharArray();
                foreach( char character in specArray ) {
                    totalChars.Add( character );
                }
            }
            totalNum = totalChars.Count;
            levelCounter = Int32.Parse( textBoxMinLength.Text );
            mainThread = new Thread( new ThreadStart( run ) );
            button1.Text = "Stop";
            running = true;
            mainThread.Start();
        } else {
            mainThread.Abort();
            button1.Text = "Start";
            running = false;
        }
    }

    private void run() {
        for( int i = 0; i < totalNum; i++ ) {
            Invoke( ( MethodInvoker ) delegate {
                write( totalChars[ i ].ToString() );
                if( i == totalNum - 1 && levelCounter == Int32.Parse( textBoxMaxLength.Text ) ) {
                    write( "\n" );
                }
            } );
            if( levelCounter < Int32.Parse( textBoxMaxLength.Text ) ) {
                levelCounter++;
                run();
            }
        }
        return;
    }

    private void write( string line ) {
        richTextBox1.Text += line;
    }

but with the setup above, and my code, the output looks like this:

aabc
bc

i think i've just made a thinking mistake, didn't i ?

so guys, do you have anny suggestions for me ?

i've also looked at the Cartesian Product, but i thought that it would not work with only one array...

thx for any help.

Answer 1

Here is an example that would generate it using recursion.

IEnumerable<string> GenerateCode(int length, int min, IEnumerable<char> chars)
{
    if (length == 0)
    {
        yield return string.Empty;
        yield break;
    }

    foreach (var mid in GenerateCode(length - 1, min, chars))
    {
        foreach (var c in chars)
        {
            var t = mid + c;
            if (length >= min)
                Console.WriteLine(t); // replace with where you want to put the results

            yield return t;
        }
    }
}

// now call this method:
GenerateCode(3 /*max length*/, 2 /*min length*/, new [] { 'a', 'b', 'c'  });

But unless this is an exercise, why would you generate all possible variations? There might be a much better solution if you provide the actual requirement.

Answer 2

You can use a backtracking algorithm, code is below. Output is also included to prove the code works.

If you need to pass parameters to a thread, see this answer.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        const int MIN_LENGTH = 2;
        const int MAX_LENGTH = 3;
        static IList<string> vals;
        static IList<string> results;

    static void go(string cur)
    {
        if (cur.Length > MAX_LENGTH)
        {
            return;
        }
        if (cur.Length >= MIN_LENGTH && cur.Length <= MAX_LENGTH)
        {
            results.Add(cur);
        }

        foreach (string t in vals)
        {
            cur += t;
            go(cur);
            cur = cur.Substring(0, cur.Length - 1);
        }
    }
    static int Main(string[] args)
    {
        vals = new List<string>();
        vals.Add("a");
        vals.Add("b");
        vals.Add("c");

        results = new List<string>();
        go("");
        results = results.OrderBy(x => x.Length).ToList();

        foreach (string r in results)
        {
            Console.WriteLine(r);
        }

        return 0;
    }
}

output

aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc

Answer 3

public static IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> source)
{
    if (source == null)
        throw new ArgumentNullException("source");
    return permutations(source.ToArray());
}

private static IEnumerable<IEnumerable<T>> permutations<T>(IEnumerable<T> source)
{
    IEnumerable<T> enumerable = source as List<T> ?? source.ToList();
    var c = enumerable.Count();
    if (c == 1)
        yield return enumerable;
    else
        for (int i = 0; i < c; i++)
            foreach (var p in permutations(enumerable.Take(i).Concat(enumerable.Skip(i + 1))))
                yield return enumerable.Skip(i).Take(1).Concat(p);
}

private static IEnumerable<string> Subsets(char[] chars)
{
    List<string> subsets = new List<string>();

    for (int i = 1; i < chars.Length; i++)
    {
        subsets.Add(chars[i - 1].ToString(CultureInfo.InvariantCulture));
        int i1 = i;
        List<string> newSubsets = subsets.Select(t => t + chars[i1]).ToList();
        subsets.AddRange(newSubsets);
    }
    subsets.Add(chars[chars.Length - 1].ToString(CultureInfo.InvariantCulture));
    return subsets;
}
private static void Main()
{
    char[] chars = new[]{'a','b','c'};
    var subsets = Subsets(chars);
    List<string> allPossibleCombPerm = 
        subsets.SelectMany(Permutations).Select(permut => string.Join("", permut)).ToList();
    allPossibleCombPerm.ForEach(Console.WriteLine);
}

Answer 4

You can use the function below. T is the type of elements that will be combined into the string (ToString() will be called on each item). You can optionally use a prefix and separator for the strings representing the combination, so they look like myprefix_A_1, myprefix_A_2, etc, where _ will be the separator.

You must call this function with level=1 and tmpList=null.

 public static IEnumerable<string> Combine<T>(string prefix, 
                                              string separator, 
                                              List<List<T>> collections, 
                                              int level, List<string> tmpList)
    {
        if (separator == null)
            separator = "";

        if (prefix == null)
            prefix = "";

        List<string> nextTmpList  = new List<string>();
        int length = collections.Count();

        if (tmpList == null || tmpList.Count == 0)
        {
            tmpList = new List<string>();
            foreach (var ob in collections.Last())
                tmpList.Add(ob.ToString());
        }

        if(length == level)
        {
            foreach (string s in tmpList)
                nextTmpList.Add(prefix + separator + s.ToString());
            return nextTmpList;
        }


        foreach (var comb in tmpList)
            foreach(var ob in collections[length - level - 1])
                nextTmpList.Add(ob.ToString() + separator + comb);
        return Combine(prefix, separator, collections, level + 1, nextTmpList);

    }

Example:

Combine<int>("G1", "_", new List<List<int>>() { new List<int>() { 1, 3}, new List<int>() {2, 4 } }, 1, null);

OUTPUT:

G1_1_2     G1_3_2    G1_1_4    G1_3_4