note
robin
That's a mighty good permutation algorithm you're using. I'm curious as to where you came across it. (A few years ago I did a fair bit of investigation into permutation generation, and this algorithm was the <a href="http://use.perl.org/~robin/journal/699">fastest pure-Perl one I could find</a> by quite a margin. Your code looks remarkably similar to mine!)
<p>
It may also be worth looking at the algorithm used in [tye]'s [cpan://Algorithm::Loops], which is jolly clever. I haven't compared it directly with this one, though if I had to guess, I would guess this one is probably still faster.
<p>
PS. I still haven't figured out how you can get away with doing nothing when <code>$copy->[-1] == @$copy</code>. What's the trick?
<p><b>Update</b>: Okay, I've got it. That's pretty clever. Here's my proof that it works.
<p>
Lemma: for every <c>$n</c> ≥ 1, there is some permutation of <c>(1..$n+1)</c> that takes more flips than any permutation of <c>(1..$n)</c>.<br>
Proof. Let <tt>@a</tt> be a permutation of <c>(1..$n)</c> that takes as many flips as possible, say it takes <tt>$flip</tt> flips; and consider the permutation <c>($n+1, reverse @a)</c>. Clearly this takes <c>($flip+1)</c> flips.
<p>
Now, if <code>$copy->[-1] == @$copy</code> then the last element can never be moved by the flipping, and so this will take the same number of flips as <c>@$copy[0..$#$copy-1]</c>. By the Lemma, this is less than the maximum number of flips.
513179
513179