[Solved]-How to understand the following C# linq code of implementing the algorithm to return all combinations of k elements from n-LINQ,C#

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

• producing combinations, part one
• producing combinations, part two
• producing combinations, part three
• producing combinations, part four
• producing combinations, part five

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.