Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re: help in understanding the standard array shuffle

by Gloom (Monk)
on Feb 14, 2001 at 18:35 UTC ( #58347=note: print w/replies, xml ) Need Help??

in reply to help in understanding the standard array shuffle

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


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 ? ...

Replies are listed 'Best First'.
Re: Re: help in understanding the standard array shuffle
by merlyn (Sage) on Feb 14, 2001 at 19:47 UTC
    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

Re: Re: help in understanding the standard array shuffle
by kschwab (Vicar) on Feb 14, 2001 at 18:59 UTC
    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: first statement, after further thought, appears to be silly.

      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)

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

      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...

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://58347]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (3)
As of 2022-01-25 17:22 GMT
Find Nodes?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:

    Results (67 votes). Check out past polls.