go ahead... be a heretic | |
PerlMonks |
Re^4: Random Derangement Of An Arrayby dcturner (Initiate) |
on Dec 08, 2008 at 19:11 UTC ( [id://729013]=note: print w/replies, xml ) | Need Help?? |
Here is a recent article describing a simpler algorithm for sampling derangements... Ah yes, that's nice. I think there is a slight buglet in the given code: $j = 1 + int rand($i-2) while $mark[$j];should read $j = 1 + int rand($i-1) while $mark[$j];should it not? Also it could hit an overflow bug for $n > 12, because d_n gets quite large quite quickly. Even with 64-bit ints you overflow for $n > 20. The same approximation works for your method as for mine: for $n > 12 the value (n-1)d_{n-2} / d_n is very close to 1/n. The iterative version of the recursive program that I wrote above is as follows. It's a bit convoluted because the recursion d_n = (n-1) (d_{n-1} + d_{n-2}) is second-order, so you have to work a bit harder than for a first-order recursion. It's also in-place and requires only a constant amount of auxiliary storage. Plus it certainly terminates, whereas the rejection method merely almost certainly terminates :) On the minus side, it is a bit quadratic (although with low probability). Side-by-side, they run pretty similarly it seems.
In Section
Seekers of Perl Wisdom
|
|