Combinations from different groups in a specific order

Question

I have a list of parameters that each accept a specific range of inputs. I am working on creating a test that creates every possible valid input. Furthermore, each group is optional (can be skipped entirely), so the combination lengths don't necessarily have to be the same length of the list.

Input

List<string[]> temp = new List<string[]>
{
    // The order of these groups is important
    new string[] { "a", "b", "c" },
    new string[] { "d", "e" },
    new string[] { "f", "g", "h" }
};

Constraints

1. 0 or 1 item per group (a string[] above)
2. Order of the List<T> must be preserved

Valid Combinations

1. a, e, f
2. a, d, g
3. c, e, f
4. b, g
5. c, f

Invalid Combinations

1. a, b, f (a and b are from the same group - not allowed)
2. a, f, d (wrong order - d must come before f)

So far, I have gone back to my library where I have a Combinations LINQ method.

public static class IEnumerableExtensions
{
    // Can be used to get all permutations at a certain level
    // Source: http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n#1898744
    public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
    {
        return k == 0 ? new[] { new T[0] } :
          elements.SelectMany((e, i) =>
            elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] { e }).Concat(c)));
    }
}

In the past I have only used this on single sequence to do things like generate every permutation of URL segments. But I am struggling with its usage on a nested list with the constraints of one per group and in a specific order.

I know I can solve this particular puzzle by doing 3 nested loops and using lists to track which items were already used, but I don't know in advance how many items will be in the List<T>, so that won't work in the general case.

How can I get all of the valid combinations of the above input?

I would prefer LINQ, but will accept any solution that solves this problem.

Answer 1

Using some extension functions,

public static IEnumerable<T> Prepend<T>(this IEnumerable<T> rest, params T[] first) => first.Concat(rest);
public static IEnumerable<T> AsSingleton<T>(this T source) {
    yield return source;
}

You can write

public static IEnumerable<IEnumerable<T>> ParametersWithEmpty<T>(this IEnumerable<IEnumerable<T>> ParmLists) {
    if (ParmLists.Count() == 0)
        yield break; // empty
    else {
        var rest = ParametersWithEmpty(ParmLists.Skip(1));
        foreach (var p in ParmLists.First()) {
            yield return p.AsSingleton(); // p.Concat(empty)
            foreach (var r in rest)
                yield return r.Prepend(p); // p.Concat(r)
        }
        foreach (var r in rest)
            yield return r; // empty.Concat(r)
    }
}

You can call it like this:

var ans = temp.ParametersWithEmpty();

To include all the levels in the results, you must skip the empty cases implicit in the above code:

public static IEnumerable<IEnumerable<T>> Parameters<T>(this IEnumerable<IEnumerable<T>> ParmLists) {
    if (ParmLists.Count() == 1)
        foreach (var p in ParmLists.First())
            yield return p.AsSingleton();
    else {
        var rest = Parameters(ParmLists.Skip(1));
        foreach (var p in ParmLists.First()) {
            foreach (var r in rest)
                yield return r.Prepend(p);
        }
    }
}

Finally, here is an alternative version that may make it somewhat clearer as it outputs the sequence as if each parameter list is preceded by empty, but also returns the all empty sequence in the answer.

public static IEnumerable<IEnumerable<T>> ParametersWithEmpty2<T>(this IEnumerable<IEnumerable<T>> ParmLists) {
    if (ParmLists.Count() == 0)
        yield return Enumerable.Empty<T>();
    else {
        var rest = ParametersWithEmpty2(ParmLists.Skip(1));
        foreach (var r in rest)
            yield return r; // empty.Concat(r)
        foreach (var p in ParmLists.First()) {
            foreach (var r in rest)
                yield return r.Prepend(p); // p.Concat(r)
        }
    }
}

Answer 2

Try following :

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

namespace ConsoleApplication1
{
    class Program
    {
        public static List<string[]> temp = new List<string[]>
        {
            // The order of these groups is important
            new string[] { "a", "b", "c" },
            new string[] { "d", "e" },
            new string[] { "f", "g", "h" }
        };
        static void Main(string[] args)
        {
            Recursive(0, new List<string>());
            Console.ReadLine();
        }
        public static void Recursive(int level, List<string> output)
        {
            if (level < temp.Count)
            {
                foreach (string value in temp[level])
                {
                    List<string> newList = new List<string>();
                    newList.AddRange(output);
                    newList.Add(value);
                    Console.WriteLine(string.Join(",", newList));
                    Recursive(level + 1, newList);
                }
            }
        }
    }
}

To get additional combinations starting with 2nd and 3rd level change main()

        static void Main(string[] args)
        {
            for (int i = 0; i < temp.Count; i++)
            {
                Recursive(i, new List<string>());
            }
            Console.ReadLine();
        }

Answer 3

Here is a Linq expression that enumerates all combinations. You can try it out in online C# repl. The idea is to use accumulator "a" to gather all combinations by going through each item of your temp collection "b" and add elements of "b" (single item combination) as well as add to every accumulated combination so far. Pretty hairy expression though.

var combinations = temp.Aggregate(Enumerable.Empty<IEnumerable<string>>(), (a, b) => a
          .Concat(b.Select(i => Enumerable.Repeat(i, 1)))
          .Concat(a.SelectMany(i => b.Select(j => i.Concat(Enumerable.Repeat(j, 1))))));