Re: help in understanding the standard array shuffle

[Gloom]

I dont know if it's efficient, but it works =)

# indexed array
@array = sort { (-1,1)[int rand 2] } @array;

# or trinary alternative
@array = sort { int rand 2 ? 1 : -1 } @array;

Hope this helps

Update

In fact, it's really a bad idea to use this for randomize an array...

See the result of this script :

#!/usr/bin/perl -w

use strict;

my @array = qw( peach banana mango orange apple cherry );
my %result;

$, = "\t\t";
$\ = "\n";

for(1..10000) {
    
    @_ = sort { (-1,1)[int rand 2] } @array;

    for(0..$#array) { $result{ $_[$_] , $_ }++ }
    
}

print '' , (0..$#array);

for my $fruit ( @array ) {
    
    print $fruit , map { $result{ $fruit , $_ } } (0..$#array);
    
}

Return :

        0     1     2     3     4     5
peach   2982  3026  2010  1095  573   314
banana  2961  2973  1960  1172  602   332
mango   1996  2004  2333  1866  1100  701
orange  1156  1116  1914  2558  1999  1257
apple   602   561   1162  2030  3171  2474
cherry  303   320   621   1279  2555  4922

Not really randomized huh ? ...

[merlyn]

The sort order is required to be 'consistent': that is, if A > B and B > C, then when asked about A and C, you'd better durn well return A > C. The underlying qsort(3) function demands it, and was optimized for it.

Because your randomizing function has no memory to guarantee this consistency, you'll be very surprised by the behavior. Older qsort functions would in fact dump core or lose data on this kind of pseudo-shuffle. Modern perls use an internal sort function that at least doesn't lose the data, but it's really not the way to do a shuffle nicely. See the FAQ solution instead, quoted at the head of this thread.

-- Randal L. Schwartz, Perl hacker

[kschwab]

See update...ugh A nit perhaps, but...:

It would seem this shuffle guarantees that no element remains in it's current position. This seems less than random.

@array= sort { (-1,0,1)[int rand 3]} @array

I suspect you never see this type of thing because of the inefficiency. The cookbook example is making length(@foo) or less comparisons, the random sort is potentially doing more than length(@foo) comparisons.

Update: Hmm...my first statement, after further thought, appears to be silly.

[extremely]

You are incorrect, the routine leaves open the possibility of keeping an item in place. Note the line next if ... there. In fact, as I recall it, that shuffle can be shown to have an even chance of producing any permutation with a true random source and is pretty damn good even with a really BAD random source.

Also, the rand trick you employ can exit early and leave chunks untouched. sortrather relies on consistency, if b>a and c>b then c>a should be implied. If I read the sort code right, violating that could lead to serious goofs like potentially never ending and such.

--
$you = new YOU;
honk() if $you->love(perl)

[kschwab]

All valid comments, but my reply wasn't to the original node, it was to Gloom's node, which was suggesting @array = sort { (-1,1)[int rand 2] } @array;.

In any case, I was nitting on the lack of a 0 return, which in light of your comments, matters little. (since random results from a sort sub are bad news...)

[arhuman]

It would seem this shuffle guarantees that no element remains in it's current position. This seems less than random.

My tests show that SOME elements stay in place !
Did I miss something ?

Note: I suspect however that the distribution is not perfect(the items "don't move too far from their position" so i suspect the "distribution" to be biased)...

Anyway it's ok for me the way it is, just have to remember it's not a true 'statistical random' change...