{"id":1263,"date":"2014-04-14T07:00:00","date_gmt":"2014-04-14T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2014\/04\/14\/enumerating-subsets-with-binomial-coefficients\/"},"modified":"2014-04-14T07:00:00","modified_gmt":"2014-04-14T07:00:00","slug":"enumerating-subsets-with-binomial-coefficients","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20140414-00\/?p=1263","title":{"rendered":"Enumerating subsets with binomial coefficients"},"content":{"rendered":"<p>\nInspired by\n<a HREF=\"http:\/\/blogs.msdn.com\/b\/oldnewthing\/archive\/2014\/03\/24\/10510315.aspx\">\nthe Little Program which enumerates set partitions<\/a>,\nI decided to do the binomial coefficients this week.\nIn other words, today&#8217;s Little Program generates\nall subsets of size <var>k<\/var> from a set of size <var>n<\/var>.\n<\/p>\n<p>\nAs before, the key is to interpret a recurrence combinatorially.\nIn general, when a recurrence is of the form\n<var>A<\/var> + <var>B<\/var>,\nit means that at the recursive step, you should do\n<var>A<\/var>, followed by <var>B<\/var>.\nIn our case, the recurrence is\n<var>C<\/var>(<var>n<\/var>, <var>k<\/var>) =\n<var>C<\/var>(<var>n<\/var> &minus; 1, <var>k<\/var>)\n+\n<var>C<\/var>(<var>n<\/var> &minus; 1, <var>k<\/var> &minus; 1).\nThe combinatorial interpretation of the recurrence is to\nlook at how you can go from a set of size\n<var>n<\/var>\nto a set of size\n<var>n<\/var> &minus; 1\nby studying the effect of removing element <var>n<\/var>.\nIf element <var>n<\/var> is not part of the subset,\nthen what&#8217;s left is a subset of size <var>k<\/var>.\nIf it is part of the subset,\nthen removing it leaves a subset of size <var>k<\/var> &minus; 1.\n<\/p>\n<p>\nTherefore, our algorithm goes like this:\n<\/p>\n<ul>\n<li>Handle base cases.\n<li>Otherwise,\n<ul>\n<li>Recursively call\n    <var>C<\/var>(<var>n<\/var> &minus; 1,\n    <var>k<\/var>) and pass the results through.<\/p>\n<li>Recursively call\n    <var>C<\/var>(<var>n<\/var> &minus; 1,\n    <var>k<\/var> &minus; 1) and add\n    element <var>n<\/var> to each of the results.\n<\/ul>\n<\/ul>\n<p>\nAs usual, once we spelled out what we&#8217;re going to do,\nactually doing it is pretty straightforward.\n<\/p>\n<pre>\nfunction Subsets(n, k, f) {\n if (k == 0) { f([]); return; }\n if (n == 0) { return; }\n Subsets(n-1, k, f);\n Subsets(n-1, k-1, function(s) {\n   f(s.concat(n));\n });\n};\n<\/pre>\n<p>\nThe first test catches the vacuous base\ncase where you say,\n&#8220;Please show me all the zero-sized subsets of a set of size <code>n<\/code>.&#8221;\nThe answer is &#8220;There is exactly one zero-sized subset,\ncalled the empty set.&#8221;\n<\/p>\n<p>\nThe second test catches the other base cases\nwhere you say,\n&#8220;Please show me all the\n<code>k<\/code>-sized subsets&sup1; of the empty set.&#8221;\nThis can&#8217;t be done if <code>k &gt; 0<\/code>, because the\nonly subset of the empty set is the empty set itself,\nand its size is not <code>k<\/code>.\n<\/p>\n<p>\nThe meat of the recurrence is pretty much what we said.\nFirst, we generate all the <code>k<\/code>-sized subsets\nfrom a set of size <code>n-1<\/code> and pass them through.\nThen we generate all the\n<code>k-1<\/code>-sized subsets\nfrom a set of size <code>n-1<\/code> and add the element <code>n<\/code>\nto them.\n<\/p>\n<p>\nWe can test out the function by logging the\nresults to the console.\n<\/p>\n<pre>\nSubsets(5, 3, <a HREF=\"http:\/\/blogs.msdn.com\/b\/oldnewthing\/archive\/2014\/03\/24\/10510315.aspx\">logToConsole<\/a>);\n<\/pre>\n<p>\nFor\n<a HREF=\"http:\/\/blogs.msdn.com\/b\/oldnewthing\/archive\/2012\/11\/13\/10367904.aspx\">\nstyle points<\/a>, we can accumulate the results in helper\nparameters.\nThis records the pending work in parameters instead of closures,\nwhich makes the code easier to port to languages which don&#8217;t support closures.\n(And probably helps the efficiency a bit too.)\n<\/p>\n<pre>\nfunction AccumulateSubsets(n, k, f, chosen) {\n if (k == 0) { f(chosen); return; }\n if (n == 0) { return; }\n AccumulateSubsets(n-1, k, f, chosen);\n AccumulateSubsets(n-1, k-1, f, [n].concat(chosen));\n};\nfunction Subsets(n, k, f) {\n AccumulateSubsets(n, k, f, []);\n}\n<\/pre>\n<p>\n(I prepend <code>n<\/code> to <code>chosen<\/code> for extra style points,\nsince it causes the results to be enumerated in a prettier order.)\n<\/p>\n<p>\nAs with Stirling numbers, we can use a destructive recursion to reduce\nmemory allocation, if we can count on the callback not modifying\nthe result.\nI&#8217;ll leave that as an exercise,\nbecause I&#8217;ve got something even better up my sleeve:\nGetting rid of the recursion entirely!\n<\/p>\n<p>\nLet&#8217;s consider the case of enumerating all the subsets of size <var>k<\/var>\nfor a fixed <var>k<\/var> known at compile-time.\nLet&#8217;s say <var>k<\/var> is 3.\nYou can structure this as a series of nested loops.\n<\/p>\n<pre>\nfunction Subsets3(n, f) {\n for (var i = 1; i &lt;= n - 2; i++) {\n  for (var j = i + 1; j &lt;= n - 1; j++) {\n   for (var k = j + 1; k &lt;= n; k++) {\n    f([i, j, k]);\n   }\n  }\n }\n}\n<\/pre>\n<p>\nThe outer loop chooses the first element,\nthe middle loop chooses the second element,\nand the inner loop chooses the last element.\nThis clearly generalizes to bigger subsets;\nyou just need more loop variables.\n<\/p>\n<p>\nWith this interpretation, you can see how to get from\none subset to the next subset:\nYou increment the last element, and if that&#8217;s not possible\nwithout violating the loop constraint,\nthen you back out one level and\ntry incrementing the next-to-last element (and restarting\nany inner loops),\nand so on,\nbacking out until you finally find an index that can be incremented\n(or give up).\n<\/p>\n<pre>\nfunction NextSubsetSameSize(s, n) {\n var k = s.length;\n \/\/ look for an index that can be incremented\n for (i = k - 1; i &gt;= 0; i--) {\n  \/\/ can this index be incremented?\n  if (s[i] &lt; n - k + i + 1) {\n   \/\/ increment it\n   s[i]++;\n   \/\/ reset all inner loops\n   while (++i &lt; k) s[i] = s[i-1] + 1;\n   return true;\n  }\n }\n return false;\n}\n<\/pre>\n<p>\nThe loop on <code>i<\/code> looks for the highest index that can be\nincremented.\nThe loop bounds depend on which index you are studying,\nsince lower indices need to leave enough room for higher indices,\nbut can you figure out the formula by looking at the pattern in\n<code>Subset3<\/code>.\nOnce we find an index with room, we increment it and reset\nall the subsequent indices to their initial values.\nIf we can&#8217;t find an index to increment, then we report failure.\n<\/p>\n<pre>\n\/\/ Enumerate all subsets of size 3 from a set of size 5\nvar s = [1, 2, 3]; \/\/ initial subset\ndo {\n console.log(JSON.stringify(s));\n} while (NextSubsetSameSize(s, 5));\n<\/pre>\n<p><b>Note<\/b>\n<\/p>\n<p>\n&sup1; In math circles, the phrase\n<i>k-sized subsets<\/i> is typically abbreviated as\n<i>k-subsets<\/i>,\nbut I chose to spell it out here because the shorthand\ntakes some getting used to.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Inspired by the Little Program which enumerates set partitions, I decided to do the binomial coefficients this week. In other words, today&#8217;s Little Program generates all subsets of size k from a set of size n. As before, the key is to interpret a recurrence combinatorially. In general, when a recurrence is of the form [&hellip;]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-1263","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>Inspired by the Little Program which enumerates set partitions, I decided to do the binomial coefficients this week. In other words, today&#8217;s Little Program generates all subsets of size k from a set of size n. As before, the key is to interpret a recurrence combinatorially. In general, when a recurrence is of the form [&hellip;]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/1263","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=1263"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/1263\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=1263"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=1263"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=1263"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}