| Date: | October 6, 2014 / year-entry #238 |
| Tags: | code |
| Orig Link: | https://blogs.msdn.microsoft.com/oldnewthing/20141006-00/?p=43913 |
| Comments: | 11 |
| Summary: | 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't gonna enumerate themselves! The traditional formulation of the recursion for Stirling numbers of the first kind (unsigned version, since it's hard to enumerate negative numbers) goes like this: c(n +... |
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't gonna enumerate themselves! The traditional formulation of the recursion for Stirling numbers of the first kind (unsigned version, since it's hard to enumerate negative numbers) goes like this: c(n + 1, k) = n · c(n, k) + c(n, k − 1). although it is more convenient from a programming standpoint to rewrite it as c(n, k) = (n − 1) · c(n − 1, k) + c(n − 1, k − 1). The Wikipedia article explains the combinatorial interpretation, which is what we will use to enumerate all the possibilities.
function Stirling1(n, k, f) {
if (n == 0 && k == 0) { f([]); return; }
if (n == 0 || k == 0) { return; }
// second term
Stirling1(n-1, k-1, function(s) { f(s.concat([[n]])); });
// first term
Stirling1(n-1, k, function(s) {
for (var i = 0; i < s.length; i++) {
for (var j = s[i].length; j > 0; j--) {
f(s.map(function(e, index) {
return i == index ? e.slice(0, j).concat(n, e.slice(j)) : e;
}));
}
}
});
}
Stirling1(5, 3, function(s) { console.log(JSON.stringify(s)); });
The inner loop could just as easily gone
for (var j = 0; j < s[i].length; j++) {
but I changed the loop control for style points. (It makes the output prettier.) |
Comments (11)
Comments are closed. |
Enough of this series.
So sad really. I don't see a good reason why Raymond can't talk about what he wants to talk about on his own blog.
The change to the j loop changes the bounds of the iteration. Are the references to j inside the loop modified to compensate? Or should they be (j-1)?
@Womble
msdn.microsoft.com/…/tkcsy6fe(v=vs.94).aspx
> The slice method copies up to, but not including, the element indicated by end.
Perhaps Raymond could have made this clearer by using (j – 1) + 1 instead of j.
@Maurits – oh, cool – I'm not a Javascript coder. Definitely scores style points :-)
WAT!
Do you need to stringify s before logging it?
>oh, cool – I'm not a Javascript coder
Look out the window.
For those people who don't have an immediate need for this knowledge in their daily lives, or their jobs: If you are at all interested in computer programming, it is ALWAYS worthwhile to see, and ruminate on, how various mathematical concepts translate into computer code. You may learn some techniques that you can apply to other problems.
Perhaps if Al Go remembered to add a :-) his comment would make more sense?
@Neil: it makes it a lot more readable. If I recall correctly, just outputting an array in javascript will get you its contents separated by commas, but the contents in this case might all be 'object'. Not sure, and didn't test it, but with stringify you will always get a readable result :)