in reply to Randomize List of items

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.

Replies are listed 'Best First'.
RE: RE: Randomize List of items
by johannz (Hermit) on May 26, 2000 at 19:55 UTC

    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]
RE: RE: Randomize List of items
by ZZamboni (Curate) on May 26, 2000 at 17:53 UTC
[reply]

In Section Cool Uses for Perl