List::Util::shuffle - where did the algorithm come from?

[Richard Gration]

Hi all,

I was just looking at List::Util::shuffle (reproduced below) and wondered
where the algorithm came from. Was this invented by the module author? Is
it a known good algorithm for shuffling lists?

It wasn't immediately obvious to me that all elements of the list would be
returned, but I understand what's going on now. Visualising pigeon holes
and bits of paper helps. A bit.

So does anyone know its provenance?

Rich

sub shuffle (@) {
my @a=\(@_);
my $n;
my $i=@_;
map {
$n = int rand($i--);
(${$a[$n]}, $a[$n] = $a[$i])[0];
} @_;
}

 

[Richard Gration]

On Thu, 25 Nov 2004 19:03:04 +0000, Richard Gration wrote:

Ah, sorry, got sidetracked. The reason I was looking at this sub is to see
if I could adapt it to not shuffle certain elements of the list based on
arbitrary criteria. "Not easily" was my answer. Can anyone suggest how I
could do this?

My shuffle code atm looks like:

for (0 .. 3 * $page->{numqs}) {
my $q1 = int rand $page->{numqs};
my $q2 = int rand $page->{numqs};
redo if ($page->{questions}->[$q1]->{qtype} =~ /^pres/
or $page->{questions}->[$q2]->{qtype} =~ /^pres/);
my $q = $page->{questions}->[$q1];
$page->{questions}->[$q1] = $page->{questions}->[$q2];
$page->{questions}->[$q2] = $q;
}

It doesn't seem to shuffle very well, particularly for lists with few
elements. That's why I was looking at List::Util::shuffle, which seemed to
do a pretty good job.

This code runs in an Apache module. I saw exactly the same series of
$q1,$q2 numbers generated in 2 consecutive requests. I thought
maybe this is because all the httpd child processes ended up with the same
random number seed. Is this possible? It seemed plausible to me because
each child is forked from the same parent, and all Perl mod init is
done in the parent, unless the mod registers a PerlChildInitHandler, which
is clearly not the case here.

TIA
Rich

 

[John Bokma]

On Thu, 25 Nov 2004 19:03:04 +0000, Richard Gration wrote:

Ah, sorry, got sidetracked. The reason I was looking at this sub is to
see if I could adapt it to not shuffle certain elements of the list
based on arbitrary criteria. "Not easily" was my answer. Can anyone
suggest how I could do this?

put elements that should be shuffled in a list, shuffle it and combine the
two.

 

[Anno Siegel]

On Thu, 25 Nov 2004 19:03:04 +0000, Richard Gration wrote:

Ah, sorry, got sidetracked. The reason I was looking at this sub is to see
if I could adapt it to not shuffle certain elements of the list based on
arbitrary criteria. "Not easily" was my answer. Can anyone suggest how I
could do this?

Use an array slice.

Suppose you want to shuffle a list of strings @l but keep all elements
in place that begin with "a".

my @mobile = grep $l[ $_] !~ /^a/, 0 .. $#l;
@l[ @mobile] = shuffle( @l[ @mobile]);

Anno