The technique you're looking for is called a shuffle. It can be done very quickly (linear time IIRC) using standard algorithms. You can try Algorithm::Numerical::Shuffle or List::Util's shuffle function.

If your data is very large, consider sorting a list of numbers corresponding to array indices, then using those numbers as array subscripts. It will avoid making a copy of your data.

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 );
[download]

Thanks eibwen,
This is the method that I ended up going with. Nice and clean and didn't require another module. Its working a treat =).

Regards Paul.

• The discussion ensued from a question: A bad shuffle,
• then it rolled on: Is this a fair shuffle?,
• ... and on: Functional shuffle,
• ... and on: Yet Another Fair Shuffle Node.

rg0now,
Thanks, its usually the first port of call... the keyword though is 'shuffle', I kept thinking 'randomly sorted list', I didn't realize shuffle was the standard term for this =P

Regards Paul

You can use rand within the sort code.

@stuff = qw[ cat dog pig cow ]; 
print "$_\n" for sort { rand() <=> rand() } @stuff
[download]

Update. I have the (theoretical) feeling that this trick may cause an infinite loop when used with a large array, but a few tests I did returned nothing suspicious.

HTH

In older Perl versions, inconsistent results from the sort block could produce core dumps or duplicated values. I don't believe modern Perl ever does that, but it's still not a way to get a fair sort.

-- Randal L. Schwartz, Perl hacker
Be sure to read my standard disclaimer if this is a reply.

No infinite loop, but Is this a fair shuffle?

---

Caution: Contents may have been coded under pressure.

I was thinking of having either a hash or array and picking a value from the list then removing that selection and repeating until the list was empty each iteration

I'd -- myself, but it doesn't let me :)
-------------------------------

The problem with that shuffle is it requires moving chunks of the array, quite inefficient with large arrays. A better linear shuffle is as follows:

use strict;
use warnings;

my ($n, $t);
my @arr = (0,1,2,3,4,5,6,7,8,9);

for (0..($#arr-1)) {
    $n = int (rand() * ($#arr - $_ + 1)) + $_;
    $t = $arr[$n];
    $arr[$n] = $arr[$_];
    $arr[$_] = $t;
}
[download]

For all items except last
    Pick random item between current item and last
    Swap that item with current item
[download]

As far as I can tell, your code is a "recoding" of the Fisher-Yates shuffle:

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];
    }
}
[download]

And permuting your version:

for (0..($#arr-1)) {
    $n = int (rand() * ($#arr - $_ + 1)) + $_;
    $t = $arr[$n];
    $arr[$n] = $arr[$_];
    $arr[$_] = $t;
}
[download]

for (0..($#arr-1)) {
    $n = int (rand() * ($#arr - $_ + 1)) + $_;
[download]

    $t = $arr[$n];
    $arr[$n] = $arr[$_];
    $arr[$_] = $t;
[download]

}
[download]

for (0..($#arr-1)) {
    $n = int (rand() * ($#arr - $_ + 1)) + $_;
[download]

    @$arr[$_,$n] = @$arr[$n,$_];
[download]

}
[download]

for (0..($#arr-1)) {
    $n = int (rand() * ($#arr - $_ + 1)) + $_;
[download]

#   next if $_ == $n;
[download]

    @$arr[$_,$n] = @$arr[$n,$_];
}
[download]

The remaining two lines are functionally equivalent:

for (0..($#arr-1)) {          # Your Version
    $n = int (rand() * ($#arr - $_ + 1)) + $_;

for ($i = @$array; --$i; ) {  # Fisher-Yates
    my $j = int rand ($i+1);
[download]

Frankly, I prefer your formulation (with the addition of the next if line) as it doesn't use an incomplete for loop, but the codes are equivalent.

UPDATE: For the benefit of the astute who realized that the remaining two lines weren't entirely equivalent:

for (0..($#arr-1)) {
    $n = int (
[download]

        rand() * ($#arr - $_ + 1)
[download]

    ) + $_;
#   next if $_ == $n;
    @$arr[$_,$n] = @$arr[$n,$_];
}
[download]

for (0..($#arr-1)) {
    $n = int (
[download]

        rand($#arr - $_ + 1)
[download]

    ) + $_;
#   next if $_ == $n;
    @$arr[$_,$n] = @$arr[$n,$_];
}
[download]

for (0..($#arr-1)) {
    $n = int (rand($#arr - $_ + 1))
[download]

        + $_
[download]

    ;
#   next if $_ == $n;
    @$arr[$_,$n] = @$arr[$n,$_];
}
[download]

Fisher-Yates traverses down the array, whereas this version traverses up the array (due to the appended + $_). Remove the addition and the codes are equivalent; leave it in and the codes are functionally equivalent.

Something in the lines of (untested):

$stuff = [ 'cat', 'dog', 'pig', 'cow' ];

my %stuff map { $_ => 1 } @$stuff;
my @elements = keys $stuff;

for ($elements[int rand scalar @elements]) {
  $stuff{$_} = 0;
  @elements = grep $_, keys %stuff;

  # your code here, $_ being either a cat, a dog, etc.

}

for (keys %stuff) { $stuff{$_} = 1 }
[download]

Do notice: I just got up! :-) If it doesn't work, that why :-) And I'm pretty sure there are better ways of doing it :-)

my $number_of_elements = 5; # arbitrary, can be anything
my @order = ();
my @base = (0 .. $number_of_elements - 1);

srand;
push @order, splice(@base, rand @base, 1) while (@base);
[download]