What I am writing is a shuffle that can be seeded to always produce exactly one permutation per seed, but that when run with different seeds (seeds that are sequential integers, with some gaps) will produce a set of permutations that are reasonably uniformly distributed. I.e., if I sort the array qw(a b c d) 2400 times using 2400 different seeds, I should expect to see each of the 24 possible permutations about 100 times (plus/minus some tolerance).

Thanks to input from dws above, here is the code I wound up using, which meets my requirements and avoids altering the seed used by rand().

use Math::Random::MT ();
sub shuffle {
    my $self = shift;
    my $seed = shift;

    my $array = $self;
# ||rand() in case no seed passed to shuffle algorithm
    my $mt = Math::Random::MT->new( $seed || rand );
    my $i;
    for($i = @$array; --$i; ) {
        my $j = int( $mt->rand($i + 1) );
        @$array[$i, $j] = @$array[$j, $i];
    }
}
[download]