Re: rand + shift || pop

[kennethk]

In addition to the lovely splice-based approaches listed above, if you are simply using your array as a grab-bag and have no need to maintain order, combining shuffle from List::Util (core) with pop or shift should yield a cleaner solution:

#!/usr/bin/perl
use strict;
use warnings;
use List::Util qw (shuffle);

my @array = (0 .. 9);
@array = shuffle @array;
print pop(@array), "\n", @array;

Note this is discussed in perlfaq4's How do I shuffle an array randomly?.

[magnus]

While splice is helpful, shuffle + shift || pop is a very simple and elegant solution. Didn't even twig on that one. Thanks very much.

[lidden]

Shuffleing is O(n) and spliceing is O(1), this may matter if your array is large.

Update: Oops, my understanding of splice was wrong. See JavaFan and ikegami below.

[JavaFan]

Actually, the expected running time of splicing is Ω(n), as a random splice will have to move n/4 elements on average.

If you want to repeatedly get a random element (without duplication), shuffle the array and use pop or shift, for a linear running time. Repeatedly splicing a random element has an expected running time of Ω(n²).

[ikegami]

It's only O(1) if you remove from the start or the end.

[davies]

If the array is being used as a grab bag and order doesn't matter, you could use the "pack of cards" algorithm I mentioned in Re: getting random number 8 times never the same and Re: Random data generation..

Regards,

John Davies