{"id":733,"date":"2014-06-16T07:00:00","date_gmt":"2014-06-16T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2014\/06\/16\/enumerating-bit-strings-with-a-specific-number-of-bits-set-binomial-coefficients-strike-again\/"},"modified":"2014-06-16T07:00:00","modified_gmt":"2014-06-16T07:00:00","slug":"enumerating-bit-strings-with-a-specific-number-of-bits-set-binomial-coefficients-strike-again","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20140616-00\/?p=733","title":{"rendered":"Enumerating bit strings with a specific number of bits set (binomial coefficients strike again)"},"content":{"rendered":"<p>\nToday&#8217;s Little Program prints all bit strings of length&nbsp;<var>n<\/var>\nsubject to the requirement that the string have exactly <var>k<\/var>\n1-bits.\nFor example, all bit strings of length 4 with 2 bits set are\n0011, 0101, 0110, 1001, 1010, and 1100.\nLet&#8217;s write\nBitString(<var>n<\/var>, <var>k<\/var>) to mean all the bit strings\nof length <var>n<\/var> with exactly <var>k<\/var> bits set.\n<\/p>\n<p>\nLet&#8217;s look at the last bit of a typical member of\nBitString(<var>n<\/var>, <var>k<\/var>).\nIf it is a zero, then removing it leaves a string one bit shorter\nbut with the same number of bits set.\nConversely every BitString(<var>n<\/var> &minus; 1, <var>k<\/var>) string\ncan be extended to a BitString(<var>n<\/var>, <var>k<\/var>) string\nby adding a zero to the end.\n<\/p>\n<p>\nIf the last bit is a one, then\nremoving it leaves a bit string of\nlength <var>n<\/var> &minus; 1 with exactly <var>k<\/var> &minus; 1 bits set,\nand conversely every bit string of length <var>n<\/var> &minus; 1 with\nexactly <var>k<\/var> &minus; 1 bits set can be extended to a bit string of\nlength <var>n<\/var> with exactly <var>k<\/var> bits set by adding a one to the end.\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    BitString(<var>n<\/var> &minus; 1,\n    <var>k<\/var>) and add a 0 to the end.<\/p>\n<li>Recursively call\n    BitString(<var>n<\/var> &minus; 1,\n    <var>k<\/var> &minus; 1) and add\n    a 1 to the end.\n<\/ul>\n<\/ul>\n<p>\nThis algorithm may look awfully familiar.\nThe overall recursive structure is the same as\n<a HREF=\"http:\/\/blogs.msdn.com\/b\/oldnewthing\/archive\/2014\/04\/14\/10516909.aspx\">\nenumerating subsets with binomial coefficients<\/a>;\nwe just decorate the results differently.\n<\/p>\n<p>\nThat&#8217;s because this problem is the same as the problem of\nenumerating subsets.\nYou can think of the set bits as selecting which elements\nget put into the subset.\n<\/p>\n<p>\nIt&#8217;s not surprising, therefore, that the resulting code\nis identical except for how we report the results.\n(Instead of generating arrays, we generate strings.)\n<\/p>\n<pre>\nfunction repeatString(s, n) {\n return new Array(n+1).join(s);\n}\nfunction BitString(n, k, f) {\n if (k == 0) { f(repeatString(\"0\", n)); return; }\n if (n == 0) { return; }\n BitString(n-1, k, function(s) { f(s + \"0\"); });\n BitString(n-1, k-1, function(s) { f(s + \"1\"); });\n}\n<\/pre>\n<p>\nIf <code>k<\/code> is zero, then that means we are looking\nfor strings of length <code>n<\/cODE>\nthat contain no bits set at all.\nThere is exactly one of those, namely the string consisting\nof <code>n<\/code> zeroes.\n<\/p>\n<p>\nIf <code>k<\/code> is nonzero but <code>n<\/code> is zero,\nthen that means we want strings of length zero with some bits set.\nThat's not possible, so we return without generating anything.\n<\/p>\n<p>\nFinally, we handle the recursive case by generating the shorter\nstrings and tacking on the appropriate digits.\n<\/p>\n<p>\nSince this is the same algorithm as subset generation,\nwe should be able to write one in terms of the other:\n<\/p>\n<pre>\nfunction BitString(n, k, f) {\n Subsets(n, k, function(s) {\n  var str = \"\";\n  for (var i = 1; i &lt;= n; i++) {\n   str += s.indexOf(i) &gt;= 0 ? \"1\" : \"0\";\n  }\n  f(str);\n });\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Today&#8217;s Little Program prints all bit strings of length&nbsp;n subject to the requirement that the string have exactly k 1-bits. For example, all bit strings of length 4 with 2 bits set are 0011, 0101, 0110, 1001, 1010, and 1100. Let&#8217;s write BitString(n, k) to mean all the bit strings of length n with exactly [&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-733","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>Today&#8217;s Little Program prints all bit strings of length&nbsp;n subject to the requirement that the string have exactly k 1-bits. For example, all bit strings of length 4 with 2 bits set are 0011, 0101, 0110, 1001, 1010, and 1100. Let&#8217;s write BitString(n, k) to mean all the bit strings of length n with exactly [&hellip;]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/733","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=733"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/733\/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=733"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=733"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=733"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}