{"id":43913,"date":"2014-10-06T07:00:00","date_gmt":"2014-10-06T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2014\/10\/06\/enumerating-cyclical-decompositions-with-stirling-numbers\/"},"modified":"2014-10-06T07:00:00","modified_gmt":"2014-10-06T07:00:00","slug":"enumerating-cyclical-decompositions-with-stirling-numbers","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20141006-00\/?p=43913","title":{"rendered":"Enumerating cyclical decompositions with Stirling numbers"},"content":{"rendered":"<p>\nThis whole enumeration nightmare-miniseries started off with\n<a HREF=\"http:\/\/blogs.msdn.com\/b\/oldnewthing\/archive\/2014\/03\/24\/10510315.aspx\">\nStirling numbers of the second kind<\/a>.\nBut what about\n<a HREF=\"http:\/\/en.wikipedia.org\/wiki\/Stirling_numbers_of_the_first_kind\">\nStirling numbers of the first kind<\/a>?\nThose things ain&#8217;t gonna enumerate themselves!\n<\/p>\n<p>\nThe traditional formulation of the\nrecursion for Stirling numbers of the first kind\n(unsigned version, since it&#8217;s hard to enumerate negative numbers)\ngoes like this:\n<\/p>\n<p>\n<var>c<\/var>(<var>n<\/var> + 1, <var>k<\/var>) =\n<var>n<\/var> &middot; <var>c<\/var>(<var>n<\/var>, <var>k<\/var>) +\n<var>c<\/var>(<var>n<\/var>, <var>k<\/var> &minus; 1).\n<\/p>\n<p>\nalthough it is more convenient from a programming standpoint to\nrewrite it as\n<\/p>\n<p>\n<var>c<\/var>(<var>n<\/var>, <var>k<\/var>) =\n(<var>n<\/var> &minus; 1) &middot; <var>c<\/var>(<var>n<\/var> &minus; 1, <var>k<\/var>) +\n<var>c<\/var>(<var>n<\/var> &minus; 1, <var>k<\/var> &minus; 1).\n<\/p>\n<p>\nThe Wikipedia article explains the combinatorial interpretation,\nwhich is what we will use to enumerate all the possibilities.\n<\/p>\n<ul>\n<li>The first term says that we recursively generate\n    the ways of decomposing <var>n<\/var> &minus; 1 items\n    into <var>k<\/var> cycles,\n    then insert element <var>n<\/var> in one of <var>n<\/var> &minus; 1 ways.<\/p>\n<li>The second term says that we recursively generate\n    the ways of decomposing <var>n<\/var> &minus; 1 items\n    into <var>k<\/var> &minus; 1 cycles,\n    then add a singleton cycle of just <var>n<\/var>.\n<\/ul>\n<pre>\nfunction Stirling1(n, k, f) {\n if (n == 0 &amp;&amp; k == 0) { f([]); return; }\n if (n == 0 || k == 0) { return; }\n \/\/ second term\n Stirling1(n-1, k-1, function(s) { f(s.concat([[n]])); });\n \/\/ first term\n Stirling1(n-1, k, function(s) {\n  for (var i = 0; i <s> 0; j--) {\n    f(s.map(function(e, index) {\n     return i == index ? e.slice(0, j).concat(n, e.slice(j)) : e;\n    }));\n   }\n  }\n });\n}\nStirling1(5, 3, function(s) { console.log(JSON.stringify(s)); });\n<\/pre>\n<p>\nThe inner loop could just as easily gone\n<\/p>\n<pre>\n   for (var j = 0; j &lt; s[i].length; j++) {\n<\/pre>\n<p>\nbut I changed the loop control for\n<a HREF=\"http:\/\/blogs.msdn.com\/b\/oldnewthing\/archive\/2012\/11\/13\/10367904.aspx\">\nstyle points<\/a>.\n(It makes the output prettier.)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This whole enumeration nightmare-miniseries started off with Stirling numbers of the second kind. But what about Stirling numbers of the first kind? Those things ain&#8217;t gonna enumerate themselves! The traditional formulation of the recursion for Stirling numbers of the first kind (unsigned version, since it&#8217;s hard to enumerate negative numbers) goes like this: c(n + [&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-43913","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>This whole enumeration nightmare-miniseries started off with Stirling numbers of the second kind. But what about Stirling numbers of the first kind? Those things ain&#8217;t gonna enumerate themselves! The traditional formulation of the recursion for Stirling numbers of the first kind (unsigned version, since it&#8217;s hard to enumerate negative numbers) goes like this: c(n + [&hellip;]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/43913","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=43913"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/43913\/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=43913"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=43913"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=43913"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}