C# Permutation of an array of arraylists?

Question

I have an ArrayList[] myList and I am trying to create a list of all the permutations of the values in the arrays.

EXAMPLE: (all values are strings)

myList[0] = { "1", "5", "3", "9" };
myList[1] = { "2", "3" };
myList[2] = { "93" };

The count of myList can be varied so its length is not known beforehand.

I would like to be able to generate a list of all the permutations similar to the following (but with some additional formatting).

1 2 93
1 3 93
5 2 93
5 3 93
3 2 93
3 3 93
9 2 93
9 3 93

Does this make sense of what I am trying to accomplish? I can't seem to come up with a good method for doing this, (if any).

Edit:
I am not sure if recursion would interfere with my desire to format the output in my own manner. Sorry I did not mention before what my formatting was.

I want to end up building a string[] array of all the combinations that follows the format like below:

for the "1 2 93" permutation

I want the output to be "val0=1;val1=2;val2=93;"

I will experiment with recursion for now. Thank you DrJokepu

Answer 1

Non-recursive solution:

foreach (String s1 in array1) {
    foreach (String s2 in array2) {
        foreach (String s3 in array3) {
            String result = s1 + " " + s2 + " " + s3;
            //do something with the result
        }
    }
}

Recursive solution:

private ArrayList<String> permute(ArrayList<ArrayList<String>> ar, int startIndex) {
    if (ar.Count == 1) {
        foreach(String s in ar.Value(0)) {
            ar.Value(0) = "val" + startIndex + "=" + ar.Value(0);
        return ar.Value(0);
    }
    ArrayList<String> ret = new ArrayList<String>();
    ArrayList<String> tmp1 ar.Value(0);
    ar.remove(0);
    ArrayList<String> tmp2 = permute(ar, startIndex+1);
    foreach (String s in tmp1) {
        foreach (String s2 in tmp2) {
            ret.Add("val" + startIndex + "=" + s + " " + s2);
        }
    }
    return ret;
}

Answer 2

Recursive solution

    static List<string> foo(int a, List<Array> x)
    {
        List<string> retval= new List<string>();
        if (a == x.Count)
        {
            retval.Add("");
            return retval;
        }
        foreach (Object y in x[a])
        {
            foreach (string x2 in foo(a + 1, x))
            {
                retval.Add(y.ToString() + " " + x2.ToString());
            }

        }
        return retval;
    }
    static void Main(string[] args)
    {
        List<Array> myList = new List<Array>();
        myList.Add(new string[0]);
        myList.Add(new string[0]);
        myList.Add(new string[0]);
        myList[0] = new string[]{ "1", "5", "3", "9" };
        myList[1] = new string[] { "2", "3" };
        myList[2] = new string[] { "93" };
        foreach (string x in foo(0, myList))
        {
            Console.WriteLine(x);
        }

        Console.ReadKey();
    }

Note that it would be pretty easy to return a list or array instead of a string by changing the return to be a list of lists of strings and changing the retval.add call to work with a list instead of using concatenation.

Answer 3

This will work no matter how many arrays you add to your myList:

        static void Main(string[] args)
        {
            string[][] myList = new string[3][];
            myList[0] = new string[] { "1", "5", "3", "9" };
            myList[1] = new string[] { "2", "3" };
            myList[2] = new string[] { "93" };

            List<string> permutations = new List<string>(myList[0]);

            for (int i = 1; i < myList.Length; ++i)
            {
                permutations = RecursiveAppend(permutations, myList[i]);
            }

            //at this point the permutations variable contains all permutations

        }

        static List<string> RecursiveAppend(List<string> priorPermutations, string[] additions)
        {
            List<string> newPermutationsResult = new List<string>();
            foreach (string priorPermutation in priorPermutations)
            {
                foreach (string addition in additions)
                {
                    newPermutationsResult.Add(priorPermutation + ":" + addition);
                }
            }
            return newPermutationsResult;
        }

Note that it's not really recursive. Probably a misleading function name.

Here is a version that adheres to your new requirements. Note the section where I output to console, this is where you can do your own formatting:

static void Main(string[] args)
        {
            string[][] myList = new string[3][];
            myList[0] = new string[] { "1", "5", "3", "9" };
            myList[1] = new string[] { "2", "3" };
            myList[2] = new string[] { "93" };

            List<List<string>> permutations = new List<List<string>>();

            foreach (string init in myList[0])
            {
                List<string> temp = new List<string>();
                temp.Add(init);
                permutations.Add(temp);
            }

            for (int i = 1; i < myList.Length; ++i)
            {
                permutations = RecursiveAppend(permutations, myList[i]);
            }

            //at this point the permutations variable contains all permutations

            foreach (List<string> list in permutations)
            {
                foreach (string item in list)
                {
                    Console.Write(item + ":");
                }
                Console.WriteLine();
            }

        }

        static List<List<string>> RecursiveAppend(List<List<string>> priorPermutations, string[] additions)
        {
            List<List<string>> newPermutationsResult = new List<List<string>>();
            foreach (List<string> priorPermutation in priorPermutations)
            {
                foreach (string addition in additions)
                {
                    List<string> priorWithAddition = new List<string>(priorPermutation);
                    priorWithAddition.Add(addition);
                    newPermutationsResult.Add(priorWithAddition);
                }
            }
            return newPermutationsResult;
        }

Answer 4

You could use factoradics to generate the enumeration of permutations. Try this article on MSDN for an implementation in C#.

Answer 5

I'm surprised nobody posted the LINQ solution.

from val0 in new []{ "1", "5", "3", "9" }
from val1 in new []{ "2", "3" }
from val2 in new []{ "93" }
select String.Format("val0={0};val1={1};val2={2}", val0, val1, val2)