Perl Monk, Perl Meditation  
PerlMonks 
Re: Speed/Efficiency tweaks for a fannkuch benchmark script?by robin (Chaplain) 
on Dec 01, 2005 at 13:34 UTC ( #513261=note: print w/ replies, xml )  Need Help?? 
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 fastest purePerl one I could find by quite a margin. Your code looks remarkably similar to mine!) It may also be worth looking at the algorithm used in tye's 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. PS. I still haven't figured out how you can get away with doing nothing when $copy>[1] == @$copy. What's the trick? Update: Okay, I've got it. That's pretty clever. Here's my proof that it works.
Lemma: for every $n ≥ 1, there is some permutation of (1..$n+1) that takes more flips than any permutation of (1..$n). Now, if $copy>[1] == @$copy then the last element can never be moved by the flipping, and so this will take the same number of flips as @$copy[0..$#$copy1]. By the Lemma, this is less than the maximum number of flips.
In Section
Seekers of Perl Wisdom

