### comment on

 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];

\$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.

```sub random_derangement {
my (\$n) = @_;

my @d = (1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496,
1334961, 14684570, 176214841);

my @t;
my \$i = \$n;
while (\$i--) {
my \$m = int(rand(\$i));
\$t[\$i] = \$m;
if (\$i <= 12) {
\$i -= 1 if (int(rand(\$d[\$i]+\$d[\$i-1])) < \$d[\$i-1]);
} else {
\$i -= 1 if (int(rand(\$i+1)) == 0);
}
}

for (\$i = 0; \$i < \$n; \$i++) {
if (defined(\$t[\$i])) {
my \$m = \$t[\$i];
\$t[\$i] = \$t[\$m];
\$t[\$m] = \$i;
} else {
my \$j = \$i+1;
my \$m = \$t[\$i+1];
while (\$j--) {
my \$k = \$j < \$m ? \$j : \$j-1;
\$t[\$j]
= \$t[\$k] < \$m ? \$t[\$k] : \$t[\$k]+1;
}
\$t[\$i+1] = \$m;
\$t[\$m] = \$i+1;
\$i += 1;
}
}

return \@t;
}

In reply to Re^4: Random Derangement Of An Array by dcturner
in thread Random Derangement Of An Array by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (8)
As of 2021-01-22 18:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The STEM quote I most wish I'd made is:

Results (243 votes). Check out past polls.

Notices?