# 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();
}
