Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

How do I shuffle an array randomly?

by faq_monk (Initiate)
on Oct 08, 1999 at 00:20 UTC ( #615=perlfaq nodetype: print w/replies, xml ) Need Help??

Current Perl documentation can be found at perldoc.perl.org.

Here is our local, out-dated (pre-5.6) version:

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:

    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.

Log In?
Username:
Password:

What's my password?
Create A New User
Chatterbox?
[sierpinski]: Haha
[Discipulus]: i'm with you!
[Discipulus]: with eskimo greeting is a little bit impressing, anyway
[Eily]: I actually used the eskimo greeting :P, I just wrote the "canonical" form of the oneliner here
[Discipulus]: next time you can add `SARGV-1` and if still not impressed pass a 'rm -f..' as last arg
[Eily]: :)

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (8)
As of 2017-04-26 15:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I'm a fool:











    Results (482 votes). Check out past polls.