Re: unsorted list

[TedPride]

EDIT: My bad. I mixed up @$array[$i,$j] with @$array[$i..$j] and misread your code. Yes, your code is functionally pretty much the same as mine, and yes, I did code a Fischer (sp?)-Yates shuffle.

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;
}

Which is equivalent to:

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

I have an expanded version (not included here) which tests this with a large number of iterations and then counts how many of each number ends up in each slot, for purposes of analyzing the randomness of the sort. The results were within a percent or two of perfectly random.

[eibwen]

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

And permuting your version:

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

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

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

}

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

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

}

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

#   next if $_ == $n;

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

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);

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 (

        rand() * ($#arr - $_ + 1)

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

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

        rand($#arr - $_ + 1)

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

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

        + $_

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

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.