CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
Search Posts SEARCH
Who's Online WHO'S
Log in LOG

Home: Perl Programming Help: Frequently Asked Questions:
How do I shuffle an array randomly?



Jan 19, 2001, 3:15 PM

Post #1 of 1 (3700 views)
How do I shuffle an array randomly? Can't Post

(From the Perl FAQ)

How do I shuffle an array randomly?

Use this:

    # fisher_yates_shuffle( \@array ) :  
# generate a random permutation of @array in place
sub fisher_yates_shuffle {
my $array = shift;
my $i;
for ($i = @$array; --$i; ) {
my $j = int rand ($i+1);
next if $i == $j;
@$array[$i,$j] = @$array[$j,$i];

fisher_yates_shuffle( \@array ); # permutes @array in place

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

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


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives