{"id":43763,"date":"2014-10-27T07:00:00","date_gmt":"2014-10-27T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2014\/10\/27\/enumerating-the-ways-of-distributing-n-balls-into-k-boxes\/"},"modified":"2014-10-27T07:00:00","modified_gmt":"2014-10-27T07:00:00","slug":"enumerating-the-ways-of-distributing-n-balls-into-k-boxes","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20141027-00\/?p=43763\/","title":{"rendered":"Enumerating the ways of distributing n balls into k boxes"},"content":{"rendered":"

\nSuppose you had n<\/var> indistinguishable balls\nand k<\/var> distinguishable boxes.\nEnumerate the ways of distributing the balls into boxes.\nSome boxes may be empty.\n<\/p>\n

\nWe can represent each distribution in the form of\nn<\/var> stars and\nk<\/var> − 1 vertical lines.\nThe stars represent balls,\nand the vertical lines divide the balls into boxes.\nFor example, here are the possible distributions for\nn<\/var> = 3,\nk<\/var> = 3:\n<\/p>\n\n\n\n\n\n\n\n\n\n\n\n
***||<\/tt><\/td>\n3+0+0<\/td>\n<\/tr>\n
**|*|<\/tt><\/td>\n2+1+0<\/td>\n<\/tr>\n
**||*<\/tt><\/td>\n2+0+1<\/td>\n<\/tr>\n
*|**|<\/tt><\/td>\n1+2+0<\/td>\n<\/tr>\n
*|*|*<\/tt><\/td>\n1+1+1<\/td>\n<\/tr>\n
*||**<\/tt><\/td>\n1+0+2<\/td>\n<\/tr>\n
|***|<\/tt><\/td>\n0+3+0<\/td>\n<\/tr>\n
|**|*<\/tt><\/td>\n0+2+1<\/td>\n<\/tr>\n
|*|**<\/tt><\/td>\n0+1+2<\/td>\n<\/tr>\n
||***<\/tt><\/td>\n0+0+3<\/td>\n<\/tr>\n<\/table>\n

\nThis visualization is known in combinatorics circles\nas\n\nstars and bars<\/a>.\n<\/p>\n

\nFrom this visualization, we see that what we are doing is\ntaking\nn<\/var> + <\/var>k<\/var> − 1 slots,\nand in each slot\nplacing a star or a bar, subject to the constraint that\nthere be n<\/var> stars and\nk<\/var> − 1 bars.\nAnother way of looking at this is that we are choosing\na subset of size\nk<\/var> − 1\nfrom a set of size\nn<\/var> + k<\/var> − 1\n(the subset specifying where the bars go).\n<\/p>\n

\nNow we can fire up\n\nour subset-generating machine<\/a>.\n<\/p>\n

\nfunction Distributions(n, k, f) {\n Subsets(n + k - 1, k - 1, function(s) {\n  s.push(n + k);\n  f(s.map(function(v, i) { return v - (s[i-1]||0) - 1; }));\n  s.pop();\n });\n}\n<\/pre>\n
\nWe ask to generate subsets of size\nk<\/var> − 1\nfrom a set of size\nn<\/var> + k<\/var> − 1.\nFor each such subset, we draw an artificial bar at the end\n(slot\nn<\/var> + k<\/var>),\nthen calculate the number of stars between the bars.\nThe number of stars between two bars is the distance between the\ntwo bars, minus 1 because the bar takes up space, too.\n<\/p>\n
\nAnother solution is to reduce this to a problem we already know\nhow to solve:\n\nenumerating integer compositions<\/a>.\nAfter distributing the balls into boxes,\nwe go around like Santa Claus and give each box one extra ball,\nwhich produces a composition.\nConversely, for any composition, remove one ball from each box,\nand you get a distribution.\n<\/p>\n
\nfunction Distributions(n, k, f)\n{\n Compositions(n + k, k, function(s) {\n  f(s.map(function(v) { return v - 1; }));\n });\n}\n<\/pre>\n
\nWe added k<\/var> extra balls, so we need to generate\ncompositions of\nn<\/var> + k<\/var>.\nWhen we get each composition, we take one ball away from\neach box and call that the distribution.<\/p>\n","protected":false},"excerpt":{"rendered":"
Suppose you had n indistinguishable balls and k distinguishable boxes. Enumerate the ways of distributing the balls into boxes. Some boxes may be empty. We can represent each distribution in the form of n stars and k − 1 vertical lines. The stars represent balls, and the vertical lines divide the balls into boxes. For […]<\/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-43763","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Suppose you had n indistinguishable balls and k distinguishable boxes. Enumerate the ways of distributing the balls into boxes. Some boxes may be empty. We can represent each distribution in the form of n stars and k − 1 vertical lines. The stars represent balls, and the vertical lines divide the balls into boxes. For […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/43763","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=43763"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/43763\/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=43763"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=43763"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=43763"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}