algorithm - Generate all combinations of selecting one element from a lot of list

Question

Lets say I have three list:

A = {"b", "c", "d", "x", "y", "z"}

B = {"a", "e", "i"}

I want to generate all combinations of selecting one element from both list.

For just 2 list this is easy (pseuodo-ish code):

combinations = []
for a in A:
    for b in B:
        combinations += [a, b]

But what if the number of lists is unknown? I want to generalize this somehow preferrably with a C# extension method.

The method signature would be something like this:

public static IEnumerable<IEnumerable<T>> Combination<T>(this IEnumerable<IEnumerable<T>> elements)

EDIT: I was looking for Cartesian product, thanks for clarification.

You're looking for the [`Cartesian product`](https://en.wikipedia.org/wiki/Cartesian_product), see here: http://stackoverflow.com/questions/3093622/generating-all-possible-combinations/3098381#3098381 — Rob, Dec 22 '15 at 23:41
Please add more requirements... for example, if you had 3 lists (show them), what is the expected result? — MaxOvrdrv, Dec 22 '15 at 23:42
@Rob Thanks, it was indeed Cartesian product I was looking for, just forgot the name. Has been some time since I last did math, thanks. — VSZM, Dec 23 '15 at 00:04

Travis J · Answer 1 · 2015-12-23T00:12:14.310

1

If you are just flat combining, and you have a set of these sets, you should be able to simply use a SelectMany on the sets.

public static IEnumerable<[T]> Combination<T>(this IEnumerable<IEnumerable<T>> elements)
{
    return elements.Select( 
        e => elements.Except(e).SelectMany( t => new T[e,t] )
    );
}

edited Dec 23 '15 at 00:12

answered Dec 22 '15 at 23:45

Travis J

81,153
41
202
273

1

This is simply adding each item against another within the same list. For example, `[1,2,3]` yields `[3, 4, 5]`. While, he's looking for: `[1,2] x [3,4]` which yields `[[1,3],[1,4],[2,3],[2,4]]` – Rob Dec 22 '15 at 23:57
@Rob - You read it wrong. Look at the signature, it is not returning a set of sets. The combination of `+` as defined here in this scope is related to the type `T`. Hey, look, this is the signature that was asked for, perhaps the addition operator was overloaded to return a set, but still, that would depend on `T`. – Travis J Dec 23 '15 at 00:00
@TravisJ Sry, Rob is right. My signature was wrong, but if you look at the pseudo code it implies as Rob says. – VSZM Dec 23 '15 at 00:09
@Rob - In the case the signature was incorrect (it would seem you were correct after all), I made an edit to indicate the creation of the arrays and changed the signature. – Travis J Dec 23 '15 at 00:13

score 0 · Answer 2 · answered Dec 22 '15 at 23:47

Assuming you want all combinations including the ones with duplicate elements in a different order, this is basically what the existing method SelectMany does.

It's fairly easy to get all combinations using query expressions and anonymous objects. Here's an example:

var combinations = from a in allAs
                   from b in allBs
                   select new { A = a, B = b };

Doing this in one fell swoop (using the proposed Combination method) would at least require you to:

Provide a function to "select" a combination (similar to the signature of the Zip method)
Or, return a generic Tuple<T, T>

But then again, it's really just replacing the usage of a cartesian product (SelectMany) and a projection (Select), both of which already exist.

algorithm - Generate all combinations of selecting one element from a lot of list

2 Answers2