.net - How to understand the following C# linq code of implementing the algorithm to return all combinations of k elements from n -


anyone can elaborate details on code or give non-linq version of algorithm:

public static ienumerable<ienumerable<t>> combinations<t>     (this ienumerable<t> elements, int k) {    return k == 0 ? new[] { new t[0] }                  : elements.selectmany(                        (e, i) =>                          elements                          .skip(i + 1)                          .combinations(k - 1)                          .select(c => (new[] {e}).concat(c))); }

the best way understand code read amazing serial post eric lippert:

basically, if have ienumerable of 5 items, , want combinations size of 3, need produce 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 , k, both non-negative. // produces sets of k elements consisting of  // integers 0 through n - 1. private static ienumerable<tinyset> combinations(int n, int k) {   // base case: if k 0 there can 1 set   // regardless of value of n: empty set set   // 0 elements.   if (k == 0)   {      yield return tinyset.empty;     yield break;   }    // base case: if n < k there can no set of   // k elements containing values 0 n - 1, because sets   // not contain repeated elements.    if (n < k)     yield break;    // set containing k elements each integer   // 0 n - 2 set of k elements each   // integer 0 n - 1, yield of those.    foreach(var r in combinations(n-1, k))     yield return r;    // if add n - 1 sets of k - 1 elements each   // integer 0 n - 2, set of k elements   // each integer 0 n - 1.    foreach(var r in combinations(n-1, k-1))     yield return r.add(n-1); }

in case, code working this:

   return k == 0      // if done, return empty array      ? new[] {new t[0]}      // each element , each number 0 enumerable size      : elements.selectmany((e, i) =>                             elements      //skip first elements, produced combination them                             .skip(i + 1)      //get combinations size k - 1                             .combinations(k - 1)      //add current element produced combinations                             .select(c => (new[] {e}).concat(c)));

this code in non-recursive form huge , unreadable, try understand recursion:

say, have 5 elements ienumerable: { 16, 13, 2, 4, 100 }, , need combinations size of 2 (total numbers of resulting sets equal binomial coefficient 5 2 = 5! / (2! * 3!) = 10)

your code producing:

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

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

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


-

Comments

Post a Comment