Explanation of getting combinations of IEnumerable recursively

Question

I recently came across the following code snippet written by Pengyang here: What is the best way to find all combinations of items in an array?

static IEnumerable<IEnumerable<T>>
    GetKCombs<T>(IEnumerable<T> list, int length) where T : IComparable
{
    if (length == 1) return list.Select(t => new T[] { t });
    return GetKCombs(list, length - 1)
        .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) > 0), 
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

Calling GetKCombs with a list { 1, 2, 3, 4 } and a length of 2 would return:

{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}

The code is working perfectly fine, but I don't understand how and why this code is working, I would appreciate if someone could explain it to me.

Welcome to Linq. Where the coolest solutions are also the ones that are the hardest to understand. — Dave, Feb 16 '16 at 20:47

score 1 · Accepted Answer · answered Feb 16 '16 at 21:23

In general what the recursive method does is that it reduces the input list into an array of single element arrays first (exit condition), and recursively adds 1 element to each of this array of single element array, to make the result into an array of 2-elements-array, and repeats the addition of 1 element continuously till the number of elements in the element-array becomes the length you need, with the one condition for addition that the last element in the array is less than the elements being added to the array from the input list. :)

(i know it is more confusing than before.. recursive LINQ does that)

So Lets take your example.

list = { 1, 2, 3, 4 }  // IEnumerable<int>, T => int
length = 2

If you notice the GetKCombs method, it is recursive till you hit the length == 1 condition..

so when you pass in length = 2, you are effectively doing this:

return list.Select(t => new T[] { t }) // we substituted the call for length = 1
        .SelectMany(t => list.Where(o => o.CompareTo(t.Last()) > 0), 
            (t1, t2) => t1.Concat(new T[] { t2 }));

the list.Select(t => new T[] { t }) basically returns an array of elements, where the elements are an 1-element-array themselves. i.e. each element in your input list.

{ {1}, {2}, {3}, {4} }

lets call this result as 'base'. with that as base, for every element in the input list again, which is greater than each element of the base result {1, 2, 3, 4} we create pairs.

i.e. for 1 in the input, we'll match 2,3,4 from base. for 2, we'll match 3 and 4. for 3, we'll match 4 this is what

list.Where(o => o.CompareTo(t.Last()) > 0

does.

once we find this pair of {1} and {2, 3, 4}, we create 2 item tuples by concatenating them in the Select query.. (t1, t2) => t1.Concat(new T[] { t2 }) to get the result set.

{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}

this becomes our new base..

because our input length = 2, we stopped here.

but if length were 3, then with this base, we would run through once more, and find that for the first element in the base {1,2} the elements in the input list, greater than the last of the first-element (2 in {1, 2}) would be 3 and 4.

so we would have 2 tuples.. {1,2,3} and {1,2,4} similarly we would have {1,3,4} similarly we would have {2,3,4}

you can see how elements in the base with last element as 4 get eliminated.

this process repeats itself till be get the tuple size we desire.

Explanation of getting combinations of IEnumerable recursively

1 Answers1