Re: unsorted list

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

Which is equivalent to:

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

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.

Comment on Re: unsorted list Select or Download Code

Replies are listed 'Best First'.
Re^2: unsorted list by eibwen (Friar) on Apr 24, 2005 at 08:35 UTC
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.	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re^2: unsorted list
by eibwen (Friar) on Apr 24, 2005 at 08:35 UTC

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.

[reply]
[d/l]
[select]