in reply to How do I shuffle an array?


shuffle( \@array );

sub shuffle
{
  my $array = shift;

  for ( my $i = 0; $i <= $#array; ++$i )
  {
    my $rand = rand($#array);
    @$array[$i,$rand] = @$array[$rand,$i];
  }
}

[download]

{Editor's note: This solution is flawed. Read Abigail-II's reply, Re: Answer: How do I shuffle an array?, for an explanation.}

Replies are listed 'Best First'.
Re: Answer: How do I shuffle an array?
by Abigail-II (Bishop) on Aug 21, 2002 at 09:53 UTC
    This "shuffles" the array, but not in a fair way. In fact, the algorithm contains two mistakes, a minor one and a severe one. Let's start with the minor one - in your loop you set $rand to rand $#array. But that means $rand could never be the last element of the array. However, fixing it that you take rand @array will not do you any good.

    Let the size of the array be N. Then at each iteration, you select from N elements (after the fix given above), and change it with the one on position $i. You do this N times. Hence, you will get NN different outcomes. There are however, only N! different permutations of the array. And since N! isn't a divisor of NN for N > 2, some outcomes will be favoured over others by your algorithm.

    Please use the Fisher-Yates shuffle as described in the FAQ. That one is fair.

    Abigail

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom