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

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

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

 



Jasmine
Administrator

Jan 19, 2001, 3:15 PM

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

(From the Perl FAQ)

How do I shuffle an array randomly?

Use this:

Code
    # 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:

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


 
 


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

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