# FAQ 4.48 How do I shuffle an array randomly?

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

•  Subject
• Author
• Posted on
This is an excerpt from the latest version perlfaq4.pod, which
comes with the standard Perl distribution. These postings aim to
reduce the number of repeated questions as well as allow the community
to review and update the answers. The latest version of the complete
perlfaq is at http://faq.perl.org .

--------------------------------------------------------------------

4.48: How do I shuffle an array randomly?

If you either have Perl 5.8.0 or later installed, or if you have
Scalar-List-Utils 1.03 or later installed, you can say:

use List::Util 'shuffle';

@shuffled = shuffle(@list);

If not, you can use a Fisher-Yates shuffle.

sub fisher_yates_shuffle {
my \$deck = shift;  # \$deck is a reference to an array
return unless @\$deck; # must not be empty!

my \$i = @\$deck;
while (--\$i) {
my \$j = int rand (\$i+1);
@\$deck[\$i,\$j] = @\$deck[\$j,\$i];
}
}

# shuffle my mpeg collection
#
my @mpeg = <audio/*/*.mp3>;
fisher_yates_shuffle( \@mpeg );    # randomize @mpeg in place
print @mpeg;

Note that the above implementation shuffles an array in place, unlike
the "List::Util::shuffle()" which takes a list and returns a new
shuffled list.

You've probably seen shuffling algorithms that work using splice,
randomly picking another element to swap the current element with

srand;
@new = ();
@old = 1 .. 10;  # just a demo
while (@old) {
push(@new, splice(@old, rand @old, 1));
}

This is bad because splice is already O(N), and since you do it N times,
you just invented a quadratic algorithm; that is, O(N**2). This does not
scale, although Perl is so efficient that you probably won't notice this
until you have rather largish arrays.

--------------------------------------------------------------------

The perlfaq-workers, a group of volunteers, maintain the perlfaq. They
are not necessarily experts in every domain where Perl might show up,
so please include as much information as possible and relevant in any
corrections. The perlfaq-workers also don't have access to every
operating system or platform, so please include relevant details for
corrections to examples that do not work on particular platforms.
Working code is greatly appreciated.

If you'd like to help maintain the perlfaq, see the details in
perlfaq.pod.

## Re: FAQ 4.48 How do I shuffle my MP3 collection?

PS> FAQ 4.48 How do I shuffle an array randomly?
PS> # shuffle my mpeg collection
PS> my @mpeg = <audio/*/*.mp3>;
PS> fisher_yates_shuffle( \@mpeg );    # randomize @mpeg in place

Well OK, but how to also minimize two songs by the same artist
(the /*/ in audio/*/*.mp3) ending up adjacent?

## Re: FAQ 4.48 How do I shuffle my MP3 collection?

On Fri, 30 Jan 2009 01:14:04 +0800 jidanni@jidanni.org wrote:

PS> FAQ 4.48 How do I shuffle an array randomly?
PS> # shuffle my mpeg collection
PS> my @mpeg = <audio/*/*.mp3>;
PS> fisher_yates_shuffle( \@mpeg );    # randomize @mpeg in place

j> Well OK, but how to also minimize two songs by the same artist
j> (the /*/ in audio/*/*.mp3) ending up adjacent?

Do a second pass on the shuffled list, extract all the clusters of
adjacent songs by the same artist, and shuffle each cluster back into
the list.  The likelihood of repeated clustering is vanishingly small.

You can also hash the song info (artist+title+byte length), which should
give you a wider spread for songs with similar info.  In other words,
similar songs will tend to end far apart, since that's a fundamental
hashing function property.  For speed, you may want to get the MD5 hash
as a number and assign it to each song.  Then you just do a sort on your
song list by the MD5 number.  If you want the shuffling to be random
each time, just add a random piece of data to each song info string
(note you need to get the random data just once at the beginning of the
algorithm, not for every song).

Finally, you can shuffle each artist's songs into a separate list and
then shuffle each artist into the big list, checking for clustering at
every insert and retrying if necessary.  This is probably the simplest
solution to implement and will give you the best results, though you
have to be careful to limit the number of retries.  It will probably be
slowest as well.

Ted

## Re: FAQ 4.48 How do I shuffle my MP3 collection?

That's a different question since it removes the randomness :)