C# string concatenation with n^n possibilities

Question

I have a generic list of string[] arrays, and I need to build a list of strings with all possible combinations of the items in those arrays. I'm having a hard time wrapping my head around the best method.

so: List mylist = new List; // I then populate this from the db...

The contents of mylist looks like this:

Buildings ||| Facilities ||| Fields ||| Files; Groups; Entity; ||| Controllers; FX; Steam;

The pipes " ||| " separate each string array in mylist, the semicolons are delimiters representing the items within each of those arrays. So the arrays have a minimum length of 1, and a max of N. I need to build a list of hyphen "---" separated strings with all possible combinations of the above, but staying in the order that they are in within the list. So using the above as an example, I would come up with this list of strings:

Buildings---Facilities---fields---Files---Controllers
Buildings---Facilities---fields---Groups---Controllers
Buildings---Facilities---fields---Entity---Controllers

Buildings---Facilities---fields---Files---Fx
Buildings---Facilities---fields---Groups---Fx
Buildings---Facilities---fields---Entity---Fx

Buildings---Facilities---fields---Files---Steam
Buildings---Facilities---fields---Groups---Steam
Buildings---Facilities---fields---Entity---Steam

If the 3rd array in the list had 2 items, instead of 1 ("Fields") - we'd have a list of 18 strings instead of 9 (3x3x2).

I tried using for loops, knowing which array had the largest length, and loop through each list item, but I just couldn't get it to work. Sleeping on it didn't really help.

anyone?

Take a look at this question. Might help: http://stackoverflow.com/questions/10515449/generate-all-combinations-for-a-list-of-strings — itsmatt, Oct 26 '12 at 15:18
You're asking for permutations of certain fields. Take a look here for some ideas: http://stackoverflow.com/questions/5128615/c-sharp-string-permutation — Reacher Gilt, Oct 26 '12 at 15:22
I'm reading these and they look relevent, but I think what I am trying to do is one more level complicated. I'm not just creating strings from a list, I'm creating them from a list of lists... (?) but at least I know what it's called a permutation now... — TheRedDwarf, Oct 26 '12 at 15:31

Nikola Davidovic · Accepted Answer · 2012-10-26T16:19:46.920

I would try recursion:

private void button1_Click(object sender, EventArgs e)
        {
            List<string[]> strs = new List<string[]>();
            strs.Add(new string[] {"Buildings"});
            strs.Add(new string[] {"Facilities"});
            strs.Add(new string[] {"Fields"});
            strs.Add(new string[] {"Files", "Groups", "Entity"});
            strs.Add(new string[] {"Controllers", "FX", "Steam"});
            List<string> list = AddStringsToList(strs, 0);

        }

        List<string> AddStringsToList(List<string[]> list, int level)
        {
            List<string> listOfStrings = new List<string>();
            if (level == list.Count - 1)
            {
                foreach (string s in list[level])
                {
                    listOfStrings.Add(s);
                }
            }
            else if(level<list.Count-1)
            {
                List<string> list1 = AddStringsToList(list, level + 1);
                foreach (string s in list[level])
                {
                    foreach(string s1 in list1)
                        listOfStrings.Add(s + "---" + s1);
                }
            }
            return listOfStrings;
        }

Tested and it works!

this is it... thank you!!!!!! also: http://pastebin.com/VzTs71u1 -- has a number of examples — TheRedDwarf, Oct 26 '12 at 16:16

Mike · Answer 2 · 2012-10-26T18:01:14.520

I think this might do what you're looking for:

static IEnumerable<string> Combinations(IEnumerable<IEnumerable<string>> items)
{
    return items.Aggregate((outs, ins) => outs.SelectMany(o => ins.Select(i => o + "---" + i)));
}

And here is an example usage

static void Main(string[] args)
{
    IEnumerable<IEnumerable<string>> items = new string[][]
    {
        new [] { "Buildings" },
        new [] { "Facilities" },
        new [] { "Fields" },
        new [] { "Files", "Groups", "Entity" },
        new [] { "Controllers", "FX", "Steam" }
    };

    foreach (var c in Combinations(items))
        Console.WriteLine(c);

    Console.ReadLine();
}

For each set of possibilities, it takes all the strings it has so far (for example "Buildings---Facilities---fields---Files", "Buildings---Facilities---fields---Entity" etc), and then for each possibility (eg { "Controllers", "FX", "Steam"}) it appends that possibility to the the output string to get a new set of output strings. The aggregation iterates this process starting at just the possibilities for the first element as the output strings, and then repeating this "Cartesian product" successively until all the input is consumed.

Edit

For reference this is the output from the sample program:

Buildings---Facilities---Fields---Files---Controllers
Buildings---Facilities---Fields---Files---FX
Buildings---Facilities---Fields---Files---Steam
Buildings---Facilities---Fields---Groups---Controllers
Buildings---Facilities---Fields---Groups---FX
Buildings---Facilities---Fields---Groups---Steam
Buildings---Facilities---Fields---Entity---Controllers
Buildings---Facilities---Fields---Entity---FX
Buildings---Facilities---Fields---Entity---Steam

I'd like to point out that this solution is quite efficient. It doesn't use recursion, which makes it particularly efficient for cases with long chains. Also, it evaluates the result lazily which is much more memory efficient if you're dealing with many result combinations (remember these combinations can grow exponentially with the chain length).

score 0 · Answer 3 · answered Oct 26 '12 at 15:50

Let's produce this instead:

Buildings---Facilities---fields---Files---Controllers
Buildings---Facilities---fields---Files---Fx
Buildings---Facilities---fields---Files---Steam

Buildings---Facilities---fields---Groups---Controllers
Buildings---Facilities---fields---Groups---Fx
Buildings---Facilities---fields---Groups---Steam

Buildings---Facilities---fields---Entity---Controllers
Buildings---Facilities---fields---Entity---Fx
Buildings---Facilities---fields---Entity---Steam

First, let's assume the data from the DB is in this format:

List<List<string>> dataFromDb;

It doesn't matter if some of the inner collections only have one value. Then something like this should do the trick:

void ConcatString(string prefix, int index, List<List<string>> collection, List<string> output)
{
    if(index == collection.Count)
    {
        output.Add(prefix);
        return;
    }
    var subCollection = collection[index];
    foreach(var str in subCollection)
    {
        string newPrefix = ((prefix.Length > 0)? "---" : "") + str;
        ConcatString(newPrefix, index+1, collection, output);
    }
}

Called like:

var output = new List<string>();
ConcatString("", 0, dataFromDb, output);

The list you're looking for should be in output. Now, please note, I haven't run this (heck, I haven't even compiled this) so you'll need to debug it but it should get you going in the correct direction at a minimum.

I tried this, and output ended up with a length of 2, values "---" and "---" — TheRedDwarf, Oct 26 '12 at 16:02

C# string concatenation with n^n possibilities

3 Answers3