{"id":513,"date":"2014-07-14T07:00:00","date_gmt":"2014-07-14T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2014\/07\/14\/enumerating-integer-compositions-the-return-of-the-binomial-coefficients\/"},"modified":"2014-07-14T07:00:00","modified_gmt":"2014-07-14T07:00:00","slug":"enumerating-integer-compositions-the-return-of-the-binomial-coefficients","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20140714-00\/?p=513","title":{"rendered":"Enumerating integer compositions (the return of the binomial coefficients)"},"content":{"rendered":"<p>In number theory,\na\n<a HREF=\"http:\/\/en.wikipedia.org\/wiki\/Composition_(number_theory)\">\ncomposition of an integer<\/a>\nis an ordered sequence of positive integers which sum to the target value.\nFor example, the value 3 can be written as\n3, 1+2, 2+1, or 1+1+1.\n<\/p>\n<p>\nYou can think about the target number as a string of stars,\nand a composition is a way of breaking the stars into groups.\nFor example, here are the compositions of 3:\n<\/p>\n<table BORDER=\"0\">\n<tr>\n<td><tt>* * *<\/tt><\/td>\n<td>3<\/td>\n<\/tr>\n<tr>\n<td><tt>*|* *<\/tt><\/td>\n<td>1+2<\/td>\n<\/tr>\n<tr>\n<td><tt>* *|*<\/tt><\/td>\n<td>2+1<\/td>\n<\/tr>\n<tr>\n<td><tt>*|*|*<\/tt>&nbsp;&nbsp;<\/td>\n<td>1+1+1<\/td>\n<\/tr>\n<\/table>\n<p>\nHow would you generate all compositions of a particular length?\nIn the above example, the compositions of length 2 would be 1+2 and 2+1.\nLet&#8217;s take a look at the last star in the composition.\nIf it is immediately preceded by a space,\nthen removing it results in a string one star shorter,\nbut with the same number of groups (but the last group is\none star smaller).\nIn other words, what&#8217;s left behind\nis a composition of <var>n<\/var> &minus; 1 of length <var>k<\/var>.\nYou can recover the original string by adding a star at the end.\n<\/p>\n<p>\nOn the other hand, if the last star is immediately preceded by a vertical\nline,\nthen removing it deletes an entire group,\nso what remains is a string one star shorter with one fewer group.\nIn other words, what&#8217;s left behind\nis a composition of <var>n<\/var> &minus; 1 of length <var>k<\/var> &minus; 1.\nYou can recover the original string by adding a separator\nand a star at 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    Compositions(<var>n<\/var> &minus; 1,\n    <var>k<\/var>) and add a star to the end.\n    (<i>I.e.<\/i>, increment the last term.)<\/p>\n<li>Recursively call\n    Compositions(<var>n<\/var> &minus; 1,\n    <var>k<\/var> &minus; 1) and add\n    a vertical line and a star to the end.\n    (<i>I.e.<\/i>, add a <tt>+1<\/tt> to the end.)\n<\/ul>\n<\/ul>\n<pre>\nfunction Compositions(n, k, f) {\n if (n == 0) { return; }\n if (k == 1) { f([n]); return; }\n Compositions(n-1, k, function(s) {\n  f(s.map(function(v, i) { \/\/ increment the last element\n    return i == s.length - 1 ? v + 1 : v;\n  }));\n });\n Compositions(n-1, k-1, function(s) {\n  f(s.concat(1)); \/\/ append a 1\n });\n}\nCompositions(5, 3, function(s) { console.log(s.join(\"+\")); });\n<\/pre>\n<p>\nOnce again,\nthis algorithm should look awfully familiar,\nbecause we&#8217;ve seen it twice before,\nonce in the context of\n<a HREF=\"http:\/\/blogs.msdn.com\/b\/oldnewthing\/archive\/2014\/04\/14\/10516909.aspx\">\nenumerating subsets with binomial coefficients<a>,\nand again when\n<a HREF=\"http:\/\/blogs.msdn.com\/b\/oldnewthing\/archive\/2014\/06\/16\/10534442.aspx\">\nEnumerating bit strings with a specific number of bits set<\/a>.\nAll we&#8217;re doing is decorating the results differently.\n<\/p>\n<p>\nHere&#8217;s a way to see directly how compositions are the same\nas subset selection.\nLet&#8217;s ignore the stars and instead look at the gaps between them.\n<\/p>\n<pre>\n* * * * *\n ^ ^ ^ ^\n<\/pre>\n<p>\nEach of the gaps can hold either a space or a vertical line.\nBreaking <var>n<\/var> into <var>k<\/var> pieces is the same as\ndrawing <var>k<\/var> &minus; 1\nvertical lines in the <var>n<\/var> &minus; 1 gaps.\nIn other words,\nyou have <var>n<\/var> &minus; 1 locations\nand you want to choose <var>k<\/var> &minus; 1 of them:\nTa da, we converted the problem into generating\nsubsets of size\n<var>k<\/var> &minus; 1 from a collection of size\n<var>n<\/var> &minus; 1.\n(In mathematics, this visualization is known as\n<a HREF=\"http:\/\/en.wikipedia.org\/wiki\/Stars_and_bars_(combinatorics)\">\nstars and bars<\/a>.)\n<\/p>\n<p>\nTherefore, we could have made the\n<code>Subsets<\/code> function do the work:\n<\/p>\n<pre>\nfunction Compositions(n, k, f) {\n Subsets(n-1, k-1, function(s) {\n  s.push(n);\n  f(s.map(function(v, i) { return v - (s[i-1]||0); }));\n  s.pop();\n });\n}\n<\/pre>\n<p>\nThe callback merely calculates the differences between\nadjacent elements of the subset, which is the number of stars\nbetween each line.\nThere is a little extra playing around in order to create\na virtual vertical bar at the beginning and end.\n<\/p>\n<p>\nSince there is an incremental way of enumerating subsets,\nthere should be an incremental way of enumerating compositions.\nIf you look at how the incremental subset enumerator works,\nyou can see how it maps to incremental composition enumeration:\nIncrementing an index is the same as moving a bar to the right,\nwhich maps to incrementing one term and decrementing the subsequent\nterm.\nResetting subsequent indices to the minimum values corresponds\nto setting the corresponding term to 1.\nThe only trick is maintaining the value of the final term,\nwhich gathers all the values squeezed out of earlier terms.\n<\/p>\n<pre>\nfunction NextComposition(s) {\n var k = s.length;\n for (var i = k - 1; i &gt;= 1; i--) {\n  if (s[i] &gt; 1) {\n   s[i]--;\n   s[i-1]++;\n   for (; i &lt; k - 1; i++) { s[k-1] += s[i] - 1; s[i] = 1; }\n   return true;\n  }\n }\n return false;\n}\n<\/pre>\n<p>\n<b>Exercise<\/b>:\nIf you wanted to generate all compositions of any length,\nyou could do it by generating all compositions of length 1,\nthen compositions of length 2, and so on up to length <var>n<\/var>.\nWhat&#8217;s the easier way of doing it?<\/p>\n<p>\n<b>Bonus chatter<\/b>:\nIf you want to generate all partitions\n(which is like compositions, except that order doesn&#8217;t matter),\nyou can use\n<a HREF=\"http:\/\/code.activestate.com\/recipes\/218332-generator-for-integer-partitions\/\">\nthis recursive version<\/a>\nor\n<a HREF=\"http:\/\/homepages.ed.ac.uk\/jkellehe\/partitions.php\">\nthis iterative one<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In number theory, a composition of an integer is an ordered sequence of positive integers which sum to the target value. For example, the value 3 can be written as 3, 1+2, 2+1, or 1+1+1. You can think about the target number as a string of stars, and a composition is a way of breaking [&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-513","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>In number theory, a composition of an integer is an ordered sequence of positive integers which sum to the target value. For example, the value 3 can be written as 3, 1+2, 2+1, or 1+1+1. You can think about the target number as a string of stars, and a composition is a way of breaking [&hellip;]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/513","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=513"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/513\/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=513"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=513"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=513"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}