score:6

Accepted answer

the best way to understand this code is to read the amazing serial post from eric lippert:

basically, if we have a `ienumerable` of 5 items, and want to get all combinations size of 3, we need to produce something like this:

``````{
// 50, 60, 70, 80, 90
{50, 60, 70},     // t   t   t   f   f
{50, 60, 80},     // t   t   f   t   f
{50, 60, 90},     // t   t   f   f   t
{50, 70, 80},     // t   f   t   t   f
{50, 70, 90},     // t   f   t   f   t
{50, 80, 90},     // t   f   f   t   t
{60, 70, 80},     // f   t   t   t   f
{60, 70, 90},     // f   t   t   f   t
{60, 80, 90},     // f   t   f   t   t
{70, 80, 90}      // f   f   t   t   t
}
``````

eric's recursive implementation:

``````// takes integers n and k, both non-negative.
// produces all sets of exactly k elements consisting only of
// integers from 0 through n - 1.
private static ienumerable<tinyset> combinations(int n, int k)
{
// base case: if k is zero then there can be only one set
// regardless of the value of n: the empty set is the only set
// with zero elements.
if (k == 0)
{
yield return tinyset.empty;
yield break;
}

// base case: if n < k then there can be no set of exactly
// k elements containing values from 0 to n - 1, because sets
// do not contain repeated elements.

if (n < k)
yield break;

// a set containing k elements where each is an integer from
// 0 to n - 2 is also a set of k elements where each is an
// integer from 0 to n - 1, so yield all of those.

foreach(var r in combinations(n-1, k))
yield return r;

// if we add n - 1 to all the sets of k - 1 elements where each
// is an integer from 0 to n - 2, then we get a set of k elements
// where each is an integer from 0 to n - 1.

foreach(var r in combinations(n-1, k-1))
yield return r.add(n-1);
}
``````

in your case, the code is working like this:

``````   return k == 0
// if we are done, return empty array
? new[] {new t[0]}
// for each element and each number from 0 to enumerable size
: elements.selectmany((e, i) =>
elements
//skip first i elements, as we already produced combination with them
.skip(i + 1)
//get all the combinations with size k - 1
.combinations(k - 1)
//add current element to all produced combinations
.select(c => (new[] {e}).concat(c)));
``````

this code in non-recursive form will be very huge and unreadable, try to understand the recursion:

say, we have a 5 elements `ienumerable`: `{ 16, 13, 2, 4, 100 }`, and we need to all the combinations from it with size of 2 (total numbers of resulting sets is equal to binomial coefficient from 5 to 2 `= 5! / (2! * 3!) = 10`)

your code will be producing:

1. for the `16` we need all the combinations of size `1`, starting from second position:
2. for the element `13` we need all the combinations of size `0` starting from the third position
3. first result: `{ 16, 13 }`
4. skip the `13`, for the element `2` we need all the combinations of size `0` starting from the fourth position
5. second result: `{ 16, 2 }`
6. skip the `13, 2`, for the element `4` we need all the combinations of size `0` starting from the fifth position
7. third result: `{ 16, 4 }`
8. skip the `13, 2, 4`, for the element `100` we need all the combinations of size `0` starting from the sixth position
9. fourth result: `{ 16, 100 }`
10. ... repeat all the above from `13`, `2`, `4`:
`{ 13, 2 }`, `{ 13, 4 }`, `{ 13, 100 }`, `{ 2, 4 }`, `{ 2, 100 }`, `{ 4, 100 }`

and we got all the 10 combinations we need. the overload the code author is using is this: `enumerable.selectmany<tsource, tresult> method (ienumerable<tsource>, func<tsource, int32, ienumerable<tresult>>)`:

selector
type: `system.func<tsource, int32, ienumerable<tresult>>`
a transform function to apply to each source element;
the second parameter of the function represents the index of the source element.

score:0

my none linq version, should be correct!

test results:

linq style:

``````123
124
125
134
135
145
234
235
245
345
``````

my way:

``````123
124
125
134
135
145
234
235
245
345
``````

my code

``````    /// <summary>
/// get the full combinations of k elements from a given list.
/// </summary>
public static list<list<t>> mycombinations<t>(this list<t> elements, int k)
{
int n = elements.count;
//given the same sequence, what if we wish to choose none of them? there does exist a subsequence which has zero elements, so we should produce it; the answer would be { { } }
if (k == 0)
{
return new list<list<t>> {new list<t> {}};
}
if (k == n)
{
return new list<list<t>> {elements};
}
// what if we have a sequence of five items and we wish to choose six of them? there is no way to do that; there is no six-element subsequence. so the answer should be { }, the empty sequence of sequences
if (k > n)
{
return new list<list<t>> {};
}
var result = new list<list<t>> {};
for (int i = 0; i < n; i++)
{
t cur = elements[i];
var rest = elements.skip(i + 1).tolist();//take out current elment to fetch combinations of the rest set
var combinationsofrest = mycombinations<t>(rest, k - 1);
var currentlist = new list<t> {cur};
foreach (list<t> combination in combinationsofrest)
{
result.add(currentlist.concat(combination).tolist());
//combination.add(cur);
//result.add(combination);
}
}
return result;
}
``````