n<\/var>.\n<\/ul>\n<\/ul>\n\nNow that we spelled out what we’re going to do,\nactually doing it is a bit anticlimactic.\n<\/p>\n
\nfunction Stirling(n, k, f) {\n if (n == 0 && k == 0) { f([]); return; }\n if (n == 0 || k == 0) { return; }\n Stirling(n-1, k-1, function(s) {\n f(s.concat([[n]])); \/\/ append [n] to the array\n });\n Stirling(n-1, k, function(s) {\n for (var i = 0; i < k; i++) {\n f(s.map(function(t, j) { \/\/ append n to the i'th subarray\n return t.concat(i == j ? n : []);\n }));\n }\n });\n}\n<\/pre>\n\nYou can test out this function by logging\nthe results to the console.\n<\/p>\n
\nfunction logToConsole(s) {\n console.log(JSON.stringify(s));\n}\nStirling(4, 2, logToConsole);\n<\/pre>\n\nLet’s walk through the function.\nThe first test catches the vacuous base\ncase where you say,\n“Please show me all the ways of breaking\nup nothing into zero blocks.”\nThe answer is, “There is exactly one way\nof doing this, which is to break it into\nzero blocks.”\nMath is cute that way.\n<\/p>\n
\nThe second test catches the other base cases\nwhere you say,\n“Please show me all the ways of breaking up\nn<\/code> elements into zero blocks”\n(can’t be done if n > 0<\/code>, because you will always\nhave elements left over),\nor you say,\n“Please show me all the ways of breaking up\n0 elements into k<\/code> blocks”\n(which also can’t be done if k > 0<\/code>\nbecause\nthere are no elements to put in the\nfirst block).\n<\/p>\n\nAfter disposing of the base cases,\nwe get to the meat of the recurrence.\nFirst, we ask for all the ways of\nbreaking\nn - 1<\/code> elements\ninto\nk - 1<\/code> blocks,\nand for each of them, we add\na single block consisting of just n<\/code>.\n<\/p>\n\nNext, we ask for all the ways of breaking\nn - 1<\/code> elements\ninto\nk<\/code> blocks,\nand for each of them, we go into a loop\nadding n<\/code> to each block.\nThe goofy map<\/code> creates a deep copy of the\narray and adds n<\/code> to the i<\/code>th block.\n<\/p>\n\nHere’s a walkthrough of the goofy map<\/code>:\n<\/p>\n\n- The
concat<\/code> method creates a new array consisting\n of the starting array with the concat<\/code> parameters\n added at the end.\n If a parameter is an array, then its elements are added;\n otherwise the parameter itself is added.\n For example,\n [1].concat(2, [3, 4])<\/code> returns\n [1, 2, 3, 4]<\/code>.\n The concat<\/code> method creates a new array,\n and a common idiom is\n s.concat()<\/code> to make a shallow copy of an array.<\/p>\n- The
map<\/code> method calls the provided callback once\n for each element of the array s<\/code>.\n The return values from all the callbacks are collected to\n form a new array, which is returned.\n For example, [1,2,3].map(function (v) { return v * 2; })<\/code>\n returns the new array [2, 4, 6]<\/code>.<\/p>\n- The
map<\/code> callback is called with the subarray\n as the first parameter and the index as the second parameter.\n (There is also a third parameter, which we don’t use.)<\/p>\n- Therefore, if all we want to do was\n create a deep copy of
s<\/code>,\n we could write\n s.map(function (t, j) { return t.concat(); })<\/code>.<\/p>\n- But we don’t want a perfect deep copy.\n We want to change the
i<\/code>th element.\n Therefore, we check the index, and if it is equal to the i<\/code>,\n then we append n<\/code>.\n Otherwise, we append []<\/code> which appends nothing.<\/p>\n- After building the array (with modifications),\n we pass it to the callback function
f<\/code>.\n<\/ul>\n\nThis pattern is common enough that maybe we should pull it into\na helper function.\n<\/p>\n
\nfunction copyArrayOfArrays(array, indexToEdit, editor) {\n return array.map(function(e, i) {\n return i === indexToEdit ? editor(e) : e.concat();\n });\n}\nfunction Stirling(n, k, f) {\n if (n == 0 && k == 0) { f([]); return; }\n if (n == 0 || k == 0) { return; }\n Stirling(n-1, k-1, function(s) {\n f(s.concat([[n]])); \/\/ append [n] to the array\n });\n Stirling(n-1, k, function(s) {\n for (var i = 0; i < k; i++) {\n f(copyArrayOfArrays(s, i, function(e) { return e.concat(n); }));\n }\n });\n}\n<\/pre>\n\nThe copyArrayOfArrays<\/code>\nfunction abstracts the goofy map<\/code>:\nYou give it an array of arrays,\nand optionally an index to edit and the function that\ndoes the editing.\nIt copies the array of arrays and calls your editor on the\nelement you want to edit.\n<\/p>\n\nTo reduce the number of memory allocations,\nthe recursion could also be done destructively.\nYou’re then counting on the callback not modifying the result,\nsince you’re going to use it again.\n<\/p>\n
\nfunction Stirling(n, k, f) {\n if (n == 0 && k == 0) { f([]); return; }\n if (n == 0 || k == 0) { return; }\n Stirling(n-1, k, function(s) {\n for (var i = 0; i < k; i++) {\n s[i].push(n);\n f(s);\n s[i].pop();<\/font>\n }\n });\n Stirling(n-1, k-1, function(s) {\n s.push([n]);\n f(s);\n s.pop();<\/font>\n });\n}\n<\/pre>\n<\/p>\n\nThe original question was about enumerating all partitions\n(Bell numbers),\nand that’s easy to put together from the Stirling numbers.\n<\/p>\n
\nfunction Bell(n, f) {\n for (var i = 1; i <= n; i++) {\n Stirling(n, i, f);\n }\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Just for fun, today’s Little Program is going to generate set partitions. (Why? Because back in 2005, somebody asked about it on an informal mailing list, suggesting it would be an interesting puzzle, and now I finally got around to solving it.) The person who asked the question said, Below we show the partitions of […]<\/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-1413","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Just for fun, today’s Little Program is going to generate set partitions. (Why? Because back in 2005, somebody asked about it on an informal mailing list, suggesting it would be an interesting puzzle, and now I finally got around to solving it.) The person who asked the question said, Below we show the partitions of […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/1413","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=1413"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/1413\/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=1413"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=1413"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=1413"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}