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

#### robin (1821)

robin
(email not shown publicly)

### Journal of robin (1821)

Wednesday August 22, 2001
12:05 PM

### In constant time!

[ #690 ]
# 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();