# A loop-free implementation of the Johnson-Trotter permutation algorithm.
# Ehrlich is responsible for the idea[1]. This implementation is mine.
# [1] Journal of the ACM: 20, 3 (July 1973), 500-513
#
# next_perm runs in constant time, every time. A longer list won't make
# it slower. Cute trick, but in practice the looping version below seems
# to be faster.
#
# 2001-08-21 robin@cpan.org
use strict;
my (@array, @p, @a, @d, @u, @c);
sub init_perm {
@array = @_;
@p = (0..$#array); # Element key => position
@a = (0..$#array); # Position => element key
@d = (-1) x @array; # Start off going left
@c = (0..$#array); # counter for each element
@u = (0..$#array); # which element to move when the counter expires
print "@array\n";
}
sub next_perm {
my ($l, $i) = (0, $u[$#u]);
return if $i == 0;
$u[$#u] = $#u;
# Switch the element keyed by $i with the one to the left/right
# of it, and update the @p and @a arrays to keep them in sync with @array.
my ($x, $y) = ($p[$i], $p[$i]+$d[$i]);
$p[$i] += $d[$i]; $p[$a[$p[$i]]] -= $d[$i];
@array[$x,$y] = @array[$y,$x]; @a[$x,$y] = @a[$y,$x];
# See if we're at one of the ends
if (--$c[$i] == 0) {
$c[$i] = $i;
$u[$i] = $u[$i-1];
$u[$i-1] = $i-1;
$d[$i] = -$d[$i];
}
1;
}
init_perm(1..shift());
print "@array\n" while next_perm();
