Calculate a set of concatenated sets of n sets

Question

Okay - I'm not even sure that the term is right - and I'm sure there is bound to be a term for this - but I'll do my best to explain. This is not quite a cross product here, and the order of the results are absolutely crucial.

Given:

IEnumerable<IEnumerable<string>> sets = 
      new[] { 
              /* a */ new[] { "a", "b", "c" },
              /* b */ new[] { "1", "2", "3" },
              /* c */ new[] { "x", "y", "z" }
            };

Where each inner enumerable represents an instruction to produce a set of concatenations as follows (the order here is important):

set a* = new string[] { "abc", "ab", "a" };
set b* = new string[] { "123", "12", "1" };
set c* = new string[] { "xyz", "xy", "x" };

I want to produce set ordered concatenations as follows:

set final = new string { a*[0] + b*[0] + c*[0], /* abc123xyz */
                         a*[0] + b*[0] + c*[1], /* abc123xy  */
                         a*[0] + b*[0] + c*[2], /* abc123x   */
                         a*[0] + b*[0],         /* abc123    */
                         a*[0] + b*[1] + c*[0], /* abc12xyz  */
                         a*[0] + b*[1] + c*[1], /* abc12xy   */
                         a*[0] + b*[1] + c*[2], /* abc12x    */
                         a*[0] + b*[1],         /* abc12     */
                         a*[0] + b*[2] + c*[0], /* abc1xyz   */
                         a*[0] + b*[2] + c*[1], /* abc1xy    */
                         a*[0] + b*[2] + c*[2], /* abc1x     */
                         a*[0] + b*[2],         /* abc1      */
                         a*[0],                 /* abc       */
                         a*[1] + b*[0] + c*[0], /* ab123xyz  */

                         /* and so on for a*[1] */
                         /* ... */

                         a*[2] + b*[0] + c*[0], /* a123xyz   */

                         /* and so on for a*[2] */
                         /* ... */

                         /* now lop off a[*] and start with b + c */

                         b*[0] + c*[0],         /* 123xyz    */

                         /* rest of the combinations of b + c
                            with b on its own as well */

                         /* then finally */
                         c[0],
                         c[1],
                         c[2]};

So clearly, there are going to be a lot of combinations!

I can see similarities with Numeric bases (since the order is important as well), and I'm sure there are permutations/combinations lurking in here too.

The question is - how to write an algorithm like this that'll cope with any number of sets of strings? Linq, non-Linq; I'm not fussed.

Why am I doing this?

Indeed, why!?

In Asp.Net MVC - I want to have partial views that can be redefined for a given combination of back-end/front-end culture and language. The most basic of these would be, for a given base view View, we could have View-en-GB, View-en, View-GB, and View, in that order of precedence (recognising of course that the language/culture codes could be the same, so some combinations might be the same - a Distinct() will solve that).

But I also have other views that, in themselves, have other possible combinations before culture is even taken into account (too long to go into - but the fact is, this algo will enable a whole bunch of really cool that I want to offer my developers!).

I want to produce a search list of all the acceptable view names, iterate through the whole lot until the most specific match is found (governed by the order that this algo will produce these concatenations in) then serve up the resolved Partial View.

The result of the search can later be cached to avoid the expense of running the algorithm all the time.

I already have a really basic version of this working that just has one enumerable of strings. But this is a whole different kettle of seafood!

Any help greatly appreciated.

Answer 1

This is my try:

void Main()
{
    IEnumerable<IEnumerable<string>> sets = 
          new[] { 
                  /* a */ new[] { "a", "b", "c" },
                  /* b */ new[] { "1", "2", "3" },
                  /* c */ new[] { "x", "y", "z" }
                };

    var setCombinations = from set in sets
                          select (from itemLength in Enumerable.Range(1, set.Count()).Reverse()
                                  select string.Concat(set.Take(itemLength).ToArray()));

    IEnumerable<string> result = new[] { string.Empty };

    foreach (var list in setCombinations) {
        result = GetCombinations(result, list);
    }
    // do something with the result
}

IEnumerable<string> GetCombinations(IEnumerable<string> root, IEnumerable<string> append) {
    return from baseString in root
           from combination in ((from str in append select baseString + str).Concat(new [] { baseString }))
           select combination;
}

Answer 2

This should produce what you want:

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

namespace SO3014119
{
    class Program
    {
        private static IEnumerable<string> GetStringCombinations(
            string prefix, 
            IEnumerable<string>[] collections, int startWithIndex)
        {
            foreach (var element in collections[startWithIndex])
            {
                if (startWithIndex < collections.Length - 1)
                {
                    foreach (var restCombination in
                        GetStringCombinations(prefix + element, collections,
                            startWithIndex + 1))
                    {
                        yield return restCombination;
                    }
                }

                yield return prefix + element;
            }
        }

        public static IEnumerable<string> GetStringCombinations(
            params IEnumerable<string>[] collections)
        {
            while (collections.Length > 0)
            {
                foreach (var comb in GetStringCombinations("", collections, 0))
                    yield return comb;

                // "lop off" head and iterate
                collections = collections.Skip(1).ToArray();
            }
        }

        static void Main(string[] args)
        {
            var a = new string[] { "a1", "a2", "a3" };
            var b = new string[] { "b1", "b2", "b3" };
            var c = new string[] { "c1", "c2", "c3" };

            foreach (string combination in GetStringCombinations(a, b, c))
            {
                Console.Out.WriteLine(combination);
            }
        }
    }
}

This produces (notice I changed the entries in the input collections to make it easier to see how they were combined):

a1b1c1
a1b1c2
a1b1c3
a1b1
a1b2c1
a1b2c2
a1b2c3
a1b2
a1b3c1
a1b3c2
a1b3c3
a1b3
a1
a2b1c1
a2b1c2
a2b1c3
a2b1
a2b2c1
a2b2c2
a2b2c3
a2b2
a2b3c1
a2b3c2
a2b3c3
a2b3
a2
a3b1c1
a3b1c2
a3b1c3
a3b1
a3b2c1
a3b2c2
a3b2c3
a3b2
a3b3c1
a3b3c2
a3b3c3
a3b3
a3
b1c1
b1c2
b1c3
b1
b2c1
b2c2
b2c3
b2
b3c1
b3c2
b3c3
b3
c1
c2
c3