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)

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