Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

robin (1821)

robin
  (email not shown publicly)
about:blank

Journal of robin (1821)

Friday August 24, 2001
01:27 PM

Faster! Faster!

[ #699 ]
# The fastest Perl permutation algorithm I've yet found. It's only 20-30% slower
# than Algorithm::PermuteInPlace.
#
# Now if we implement _this_ in C, with a Perl callback for processing
# the permutation, we can probably get even faster than Algorithm::PermuteInPlace.
# (There are ways to invoke Perl callbacks without the normal subcall overhead.)

# Translated from the C code by Matt Day,
#     at http://www.cs.jyu.fi/~hirvonen/opk_2001_ratk/permu.txt

use strict;

sub permute {
    my ($aref, $level) = (@_, 0);
    my ($index, $copy, $printing) = ($level, [@$aref], $level+1 == @$aref);
    do {
        if ($printing) {
            print "@$copy\n";
        } else {
            permute($copy, 1+$level);
        }
        @$copy[$index-1, $index] = @$copy[$index, $index-1]
            if $index != 0;

    } while $index-- > 0;
}

permute([1..shift]);