Finding all combinations from sets of possibilitie

Question

I have multiple sets of arrays that contain additional arrays that have values attached that I use for figuring out math. In order to find the best combination of these things, I need to mix and match from these arrays. I've seen "solutions" similar to this around, but they're usually 1 array deep with no real combinations/possibilities. So to give an example.

I have sets A, B, and C. Set A contains Aa, Ab, Ac, and Ad. Aa contains a set of values. Extrapolate that out for the others. Aa can only be compared with Ba and Ca. How do I go about writing a program to find all combinations(i.e. Aa, Ab, Cc, Bd compared with Ba, Cb, Ac, Bd and etc) so I can compare the math on each combination to find the best one? Note: this is just an example, I don't need it for specifically 3 sets of 4 sets of 4, it needs to be able to expand.

Now I know I didn't use very meaningful names for my variables, but I would appreciate if any code given does have meaningful names in it(I'd really rather not follow around variables of x and c around in code).

Answer 1

The accepted answer appears to be correct but is a very strange way to do a Cartesian product in C#. If you have a given number of sequences you can take their Cartesian product idiomatically like this:

    var aList = new[] { "a1", "a2", "a3" };
    var bList = new[] { "b1", "b2", "b3" };
    var cList = new[] { "c1", "c2", "c3" };
    var product = from a in aList
                  from b in bList
                  from c in cList
                  select new[] { a, b, c };

    foreach (var p in product)
        Console.WriteLine(string.Join(",", p));

If you have arbitrarily many sequences that you need to take their Cartesian product then you can do it like this:

static class Extensions
{
  public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    this IEnumerable<IEnumerable<T>> sequences) 
  { 
    IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() }; 
    return sequences.Aggregate( 
      emptyProduct, 
      (accumulator, sequence) => 
        from accseq in accumulator 
        from item in sequence 
        select accseq.Concat(new[] {item})); 
  }
}

And then:

    var aList = new[] { "a1", "a2", "a3" };
    var bList = new[] { "b1", "b2", "b3" };
    var cList = new[] { "c1", "c2", "c3" };
    var lists = new[] { aList, bList, cList };
    var product = lists.CartesianProduct();
    foreach (var p in product)
        Console.WriteLine(string.Join(",", p));

See

http://ericlippert.com/2010/06/28/computing-a-cartesian-product-with-linq/

and my answer to

Generating all Possible Combinations

for more discussion of this problem.

Answer 2

Assuming you are using a version of C# which supports LINQ:

static void Main(string[] args)
    {
        // declare some lists
        var aList = new string[] { "a1", "a2", "a3" };
        var bList = new string[] { "b1", "b2", "b3" };
        var cList = new string[] { "c1", "c2", "c3" };

        // do the equivalent of a SQL CROSS JOIN
        var permutations = aList
            .Join(bList, a => "", b => "", (a, b) => new string[] { a, b })
            .Join(cList, ab => "", c => "", (ab, c) => new string[] { ab[0], ab[1], c });

        // print the results
        Console.WriteLine("Permutations:");
        foreach (var p in permutations)
            Console.WriteLine(string.Join(", ", p));
    }

The Join calls with the lambda expressions pointing the strings to empty strings causes the Join function to treat the strings as equal, emulating a SQL CROSS JOIN.