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

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
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[\$i])[0];
} @_;
}

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

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->) {
my \$q1 = int rand \$page->;
my \$q2 = int rand \$page->;
redo if (\$page->->[\$q1]-> =~ /^pres/
or \$page->->[\$q2]-> =~ /^pres/);
my \$q = \$page->->[\$q1];
\$page->->[\$q1] = \$page->->[\$q2];
\$page->->[\$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

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

Richard Gration wrote:

> 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.

--
John                   Small Perl scripts: http://johnbokma.com/perl/
Perl programmer available:     http://castleamber.com/
Happy Customers: http://castleamber.com/testimonials.html

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

> 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

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

> 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[\$i])[0];
>   } @_;
> }

See "Seminumerical Algorithms", 2nd Ed., D. Knuth, Section 3.4.2
"Random Sampling and Shuffling", Algorithm P (Shuffling), p. 139, and
references therein.