Combinations of multiple list

Question

I'm not completely sure that the term 'Combination' is correct, however I have a requirement to build a list of combination form one or more List. Each list will contain a varying number of elements, e.g.

List<string> lBag1 = ["1_0, 1_1, 1_3"]
List<string> lBag2 = ["11_0, 11_1, 11_8"]
List<string> lBag3 = ["3_0"]

What I need is all combination of the Lists form 1 to n elements with no more than one element from each list, e.g.

"1_0"
"1_1"
"1_3"
"11_0"
"11_1"
"11_8"
"3_0"
"1_0 11_0"
"1_0 11_1"
"1_0 11_8"
"1_0 3_0"
...
"1_3 11_8 3_0"

Order is not important, so "1_0 11_0" is considered the same as "11_0 1_0".

Any assistance would be greatly appreciated

Check this question http://stackoverflow.com/questions/545703/combination-of-listlistint?lq=1 — tranceporter, Sep 18 '12 at 09:39
@Dialecticus - no, 3 is probably the most common but there can be any number — markpirvine, Sep 18 '12 at 09:59
@DanPuzey I have read http://www.codeproject.com/Articles/26050/Permutations-Combinations-and-Variations-using-C-G, however adapting it to an unknown number of Lists is where I have a problem — markpirvine, Sep 18 '12 at 10:01

score 1 · Answer 1 · answered Sep 18 '12 at 09:06

Does this work for you:

var empty = new string[] { null, };

var query =
    from b1 in empty.Concat(lBag1)
    from b2 in empty.Concat(lBag2)
    from b3 in empty.Concat(lBag3)
    let bs = new [] { b1, b2, b3 }.Where(b => b != null)
    let result = String.Join(" ", bs)
    where result != ""
    select result;

Rawling · Accepted Answer · 2012-09-18T10:31:37.543

These two extension methods will let you chain together several enumerations, calculating the combinations you want.

Each combination is an enumeration, rather than a concatenated string.

// This method takes two sequences of T, and returns
//  - each element of the first sequence,
//        wrapped in its own one-element sequence
//  - each element of the second sequence,
//        wrapped in its own one-element sequence
//  - each pair of elements (one from each sequence),
//        as a two-element sequence.
// e.g. { 1 }.CrossWith({ 2 }) returns { { 1 }, { 2 }, { 1, 2 } }
public static IEnumerable<IEnumerable<T>> CrossWith<T>(
    this IEnumerable<T> source1,
    IEnumerable<T> source2)
{
    foreach(T s1 in source1) yield return new[] { s1 };
    foreach(T s2 in source2) yield return new[] { s2 };
    foreach(T s1 in source1)
        foreach(T s2 in source2)
            yield return new[] { s1, s2 };
}

// This method takes a sequence of sequences of T and a sequence of T,
//     and returns
//  - each sequence from the first sequence
//  - each element of the second sequence,
//        wrapped in its own one-element sequence
//  - each pair, with the element from the second sequence appended to the
//        sequence from the first sequence.
// e.g. { { 1, 2 } }.CrossWith({ 3 }) returns
//      { { 1, 2 }, { 3 }, { 1, 2, 3 } }
public static IEnumerable<IEnumerable<T>> CrossWith<T>(
    this IEnumerable<IEnumerable<T>> source1,
    IEnumerable<T> source2)
{
    foreach(IEnumerable<T> s1 in source1) yield return s1;
    foreach(T s2 in source2) yield return new[] { s2 };
    foreach(IEnumerable<T> s1 in source1)
        foreach(T s2 in source2)
            yield return s1.Concat(new[] { s2 }).ToArray();
}

var cross = lBag1.CrossWith(lBag2).CrossWith(lBag3);
// { "1_0" }, { "1_1" }, { "1_3" } ...
// ... { "1_0", "11_0" }, ...

Alternatively, there is this classic Eric Lippert blog post that does a similar thing. (Similar result, very different method.)

I've quickly tested this code and it seems to give me exactly what I need - thanks! Would you be able to explain a little more how it works? — markpirvine, Sep 18 '12 at 10:12

score 0 · Answer 3 · answered Sep 18 '12 at 09:11

This is only my opinion. You have to decide by your own how to implement it, but i would:

1) Create a class to represent your pairs X_Y

2) Make your class Implement IEquatable

3) Provide implementations for Equal

4) Implement a constructor that, given a string in the form X_Y returns a YourClass object.

5) Implement a public static function that, given a string containing comma separatd list of X_Y returns a List

6) Use the previous method to create three list.

7) Create an empty List

8) Use yourList.Append to add elements from the trhee lists.

May be I use guns to kill flies.

Combinations of multiple list

3 Answers3

Linked