Given a list of items, put them in random order without creating a new list.

With a run of 100,000, randomizing the alphabet, the distribution was mostly even, with a slight bias of items at the front of the list tending to wind up after the mid-point and items at the rear tending to wind up before the mid-point. For the 100,000 runs, the first item's average position was 1 past the mid-point, while the last item's average position was 1 before the mid-point. But this is close enough to a perfect shuffle for most uses.

my @lList = (1..10);
my ($lPos, $lRand);
# For every position in the list, swap it with a random
# position earlier in the list.
foreach $lPos (1..$#list) {
  $lRand = int(rand($lPos));
  @lList[$lPos, $lRand] = @lList[$lRand, $lPos];
}

[download]

To correct the bias, use the following code:

my @lList = (1..10);
my ($lPos, $lRand);
# For every position in the list, swap it with a random
# position earlier in the list.
foreach $lPos (1..$#list) {
  $lRand = int(rand($lPos+1));
  @lList[$lPos, $lRand] = @lList[$lRand, $lPos];
}

[download]

Replies are listed 'Best First'.
RE: Randomize List of items
by gregorovius (Friar) on May 19, 2000 at 09:47 UTC
    Here's another way to do it: 
    #!/usr/bin/perl -w
use strict;

my @oldList = (1 .. 50);

my @newList =
  map { $_->[0] }
  sort { $a->[1] <=> $b->[1] }
  map { [$_, rand] } @oldList;

print "Numbers:\n", (join "-", @newList), "\n";

    [download]
    Use the Schwartz, Luke!
[reply]
[d/l]
RE: Randomize List of items
by KM (Priest) on May 26, 2000 at 18:11 UTC
    The non-biased version you showed has a name, it is the Fisher-Yates shuffle. You can learn about the algorythm ib the original publishing Statistical Tables, from 1938, or in Knuth's The Art of Computer Programming, vol2, and I believe the Perl Cookbook. You can use the Tie::Pick module, which has a variant of the FY, or, Algorithm::Numerical::Shuffle, which uses FY:

    use Algorithm::Numerical::Shuffle qw(shuffle);
my @array = shuffle qw /one two three four/;

    [download]

    Algorythms using splice() can be slower for larger arrays.

    Cheers,
    KM

[reply]
[d/l]
RE: Randomize List of items
by athomason (Curate) on May 19, 2000 at 03:08 UTC
    If concise code appeals to you more than saving memory, here's a quick hack to created a randomized version of an exsting list:
    my @newList = sort {rand > .5} @oldList;

    [download]
    I think the randomization is complete... can anybody see a reason why it wouldn't be?
[reply]
[d/l]
      On just a few test runs, (not a statistically significant sample size) this appears to have a tendency to leave parts of the original list in order (elements in original list tend to stay in the same order after sorting).

      78945612103
      71014568932
      10924567831
      68715491032
      10194567823
      78106519234
      81096571342
      86935721041
      76891023514
      61081547932
      10876549231 (interesting: mostly reversed)

      80, 79, 75, 67, 65, 57, 72, 62, 71, 61, 52, 95, 68, 87, 83, 82, 59, 78, 58, 77, 100, 64, 88, 97, 99, 74, 96, 1, 94, 3, 4, 98, 6, 8, 15, 17, 20, 22, 24, 26, 30, 31, 33, 34, 38, 39, 40, 44, 49, 50, 51, 53, 54, 55, 56, 60, 63, 66, 69, 70, 73, 76, 81, 84, 85, 86, 89, 90, 91, 92, 93, 35, 36, 10, 29, 48, 7, 32, 28, 42, 25, 47, 16, 41, 14, 46, 13, 45, 12, 11, 43, 9, 5, 21, 23, 37, 2, 18, 27, 19

      91, 52, 84, 85, 86, 53, 88, 56, 51, 59, 94, 74, 72, 83, 61, 54, 95, 81, 82, 78, 55, 96, 2, 97, 4, 98, 99, 7, 100, 10, 13, 15, 17, 19, 20, 22, 26, 27, 28, 31, 32, 34, 35, 37, 38, 41, 42, 43, 47, 50, 57, 58, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 73, 75, 76, 77, 79, 80, 87, 89, 90, 92, 93, 33, 48, 49, 40, 12, 1, 3, 5, 46, 8, 36, 14, 45, 44, 30, 11, 9, 39, 29, 16, 18, 24, 25, 23, 6, 21

      93, 95, 78, 79, 99, 90, 74, 61, 92, 77, 100, 64, 98, 97, 63, 73, 85, 67, 54, 56, 80, 1, 2, 89, 4, 91, 6, 94, 8, 96, 10, 14, 15, 18, 21, 23, 24, 25, 27, 29, 30, 31, 34, 37, 39, 41, 45, 47, 49, 50, 51, 52, 53, 55, 57, 58, 59, 60, 62, 65, 66, 68, 69, 70, 71, 72, 75, 76, 81, 82, 83, 84, 86, 87, 88, 20, 35, 17, 33, 19, 22, 48, 3, 11, 46, 44, 38, 40, 36, 32, 16, 13, 12, 9, 7, 26, 42, 43, 28, 5

      I don't have the mathematical background to correctly analyze this, but based on what I know about quicksort, this doesn't surprise me a lot. It feels strange, anyway.

      This kind of stuff makes me wish I'd taken more math, but my intuition tells me Bruce Schneier would not approve... :-)

[reply]
      It's not very random. Try this sample program: 
      #!/usr/bin/perl -w

use strict;

my @oldList = (1 .. 100);
my @newList = sort {rand > .5} @oldList;

print "Numbers:\n", (join "\n", @newList), "\n";

      [download]
      I see a lot of clumping.
[reply]
[d/l]
        It looked reasonably random to me. I ran it through the same program I ran my snippet through and got similar results. Maybe slightly less uniform than mine, but still reasonable.
        Here is the code I used to test these. I create a list of 100 items, and randomize that list and record the resulting positions 100,000 times. The average positions for each number should hover around the mid-point of the list. Both of these do. Here's the code( yes, it's a quick hack!)
        #!/usr/bin/perl

print `date`;

my %count;
my $size = 100000;
foreach (0..99) {
    $count{$_} = 0;
};
my @lKeys = sort { $a <=> $b } (keys(%count));
my $arraySize = scalar(@lKeys);
for (1..$size) {
    my @lList = crypto(\@lKeys);
    my $pos = 0;
    my $curr = '';
    while (defined($curr = shift(@lList))) {
        $count{$curr} += $pos;
        $pos++;
    }
}

local $\ = "\n";
print "Size:$size";
print "Array Size: $arraySize\n";
foreach my $curr (@lKeys) {
    my $total = $count{$curr};
    my $average = $total/$size;
    my $diff = abs(($arraySize/2)-$average);
    print "$curr:\t$diff";
}

print `date`;
exit;

sub crypto {
    my $rList = shift;
    my @list = @$rList;
    
    my ($lPos, $lRand);
    foreach $lPos (1..$#list)
    {
        $lRand = int(rand($lPos+1));
        @list[$lPos, $lRand] = @list[$lRand, $lPos];
    }
    return @list;
}

sub otherCrypto {
    my $rList = shift;
    my @list = sort {rand > .5} @$rList;
    return @list;
}

        [download]
        If there is a problem with my methodology for testing this, I would appreciate it being pointed out.
[reply]
[d/l]

      Looks random to me. Check this out: 

      $loop=5;
{
$total=100000;
for (1..$total) {
  rand > .5 and $x++ and next;
  $y++;
}
$xp=$x/$total*100; $yp=$y/$total*100;
$xd=50-$xp; $yd=50-$yp;
print "X: $x ($xp%) $xd\nY: $y ($yp%) $yd\n";
$loop-- and redo;
}

      [download]

      Results: 

      X: 49790 (49.79%) 0.210000000000001
Y: 50211 (50.211%) -0.210999999999991
X: 50071 (50.071%) -0.070999999999998
Y: 49930 (49.93%) 0.0700000000000003
X: 49781 (49.781%) 0.219000000000001
Y: 50220 (50.22%) -0.219999999999999
X: 50080 (50.08%) -0.0800000000000054
Y: 49921 (49.921%) 0.0790000000000006
X: 49898 (49.898%) 0.102000000000004
Y: 50103 (50.103%) -0.102999999999994
X: 50033 (50.033%) -0.0330000000000084
Y: 49968 (49.968%) 0.0319999999999965

      [download]
[reply]
[d/l]
[select]
RE: Randomize List of items
by Alokito (Novice) on May 26, 2000 at 08:57 UTC
    Bah, all the solutions I have seen either violate the order not to create new lists, or seem to produce biased results. I think I have found a way to do neither.

    Clearly, if we pick items randomly from the original list without replacement, we will generate a completely random ordering of the list. That is what the following code effectively does. 

    my @a = (1 .. 10);
print join("\t", @a),"\n";
#starting from the end and working back
for ($i = $#a; $i > 0; $i--) {
    # pick a random guy to stuff in the ith slot
    $guy = int(rand($i + 1));
    #snatch the guy out, and stuff him in!
    splice(@a, $i, 0, splice(@a, $guy, 1));
}
print join("\t", @a),"\n";

    [download]
    It's a bit like pretending that we're making another list, but swapping things around using splice instead. Notice that the one guy that we never picked ends up as the first element in the array. Splice is cool.
[reply]
[d/l]

      I'm not sure how your algorithm is different then mine. You start from the back, I start from the front, but if you compare the two side-by-side, they are almost identical.

      My Original post - Non-Biased version Alokito's version Fisher-Yates Shuffle
      my @lList = (1..10); my @a = (1 .. 10); my $array = shift;
      my ($lPos, $lRand); print join("\t", @a),"\n"; my $i;
      # For every position in the list, swap it with a random
      # position earlier in the list.      		 #starting from the end and working back
      foreach $lPos (1..$#list) { for ($i = $#a; $i > 0; $i--) { for ($i = @$array; --$i; ) {
          # pick a random guy to stuff in the ith slot
          $lRand = int(rand($lPos+1));     $guy = int(rand($i + 1));     my $j = int rand ($i+1);
          #snatch the guy out, and stuff him in!     next if $i == $j;
          @lList$lPos, $lRand = @lList$lRand, $lPos;     splice(@a, $i, 0, splice(@a, $guy, 1));     @$array$i,$j = @$array$j,$i;
      } } }
      print join("\t", @a),"\n";

      When I posted this, I had not realized it was so similar to the one in the faq, the fisher_yates_shuffle. The only real difference is fisher-yates does not allow an element to stay in the same position. I don't think this is necessary. If someone knows why this is done, I would love to learn it.

      Alokito,
      You seem to imply that my solution either does not randomize in place, or is biased. To quote:

      Bah, all the solutions I have seen either violate the order not to create new lists, or seem to produce biased results. I think I have found a way to do neither.
      But the truth is, our code does almost the same thing, just from different directions. Am I missing something?

[reply]
[reply]

Back to Cool Uses for Perl