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 July 27, 2001
04:10 PM

Johnson-Trotter

[ #517 ]
# A non-recursive implementation of the Johnson-Trotter permutation algorithm.
#
# The easiest way to understand the code is to stare at the output:
# it's pretty easy to see what's happening, and when you've seen that,
# think about how you'd implement it. You should end up with something
# similar to what's here.
#
# 2001-07-27 robin@cpan.org

use strict;
my @array = (qw'a b c X');

my @p = (0..$#array);    # Start at the end...
my @d = (-1) x @array;    # ...going left

sub next_perm {
    my ($l, $i) = (0, $#p);

    while ($i > 0
      && ( ($p[$i] == 0 && $d[$i] < 0)
        || ($p[$i] == $i && $d[$i] > 0)) )
    {
        ++$l if $p[$i] == 0;
        $d[$i] = -$d[$i];
        -- $i;
    }

    my $p_l = $p[$i]+$l;   my $p_l_d = $p_l + $d[$i];
    $p[$i] += $d[$i];

    @array[$p_l, $p_l_d] = @array[$p_l_d, $p_l];
}

for(1..25) {
    print "@array\n";
    next_perm();
}