FAQ 4.48 How do I shuffle an array randomly?
in [Perl]
|
Prev: FAQ 3.23 Can I write useful Perl programs on the command line?
Next: FAQ 4.47 How do I handle circular lists?
From: PerlFAQ Server on 27 Jun 2010 00:00 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. |