Easy to see with a small concrete example: the list {1,2,3} has 3!=6
possible permutations, but your routine makes one of 3^3=21 different
swap sequences.  Since 21 is not a multiple of 6, some of the 6
permutations must be more likely than others.





On 4/14/08, Mark J. Reed <[log in to unmask]> wrote:
> Yes, if you randomly swap over the whole range, the shuffle is biased.
>  Relevant snippet from Wikipedia article on F-Y shuffle:
>
> "... always selecting k from the entire range of valid array indexes
> on every iteration (i.e. using k = rng.nextInt(array.length) in the
> Java example above) also produces a result which is biased, albeit
> less obviously so. This can be seen from the fact that doing so yields
> N^N distinct possible sequences of swaps, whereas there are only N!
> possible permutations of an N-element array. Since N^N can never be
> evenly divisible by N! (as the latter is divisible by N-1, which
> shares no prime factors with N), some permutations must be produced by
> more of the N^N sequences of swaps than others.
>
>
>
> On 4/14/08, Nigel Garvey <[log in to unmask]> wrote:
> > "Mark J. Reed" wrote on Sun, 13 Apr 2008 18:06:11 -0400:
> >
> > >My code is a complete solution. No need to change it, other than to
> > >correct my syntax errors.  Here's the corrected version:
> > >
> > >on shuffle(aList)
> > >	set listSize to count aList
> > >	repeat with i from listSize to 2 by -1
> > >		set j to random number from 1 to i
> > >		if j is not i then
> > >			tell aList to set {item i, item j} to {item j, item i}
> > >		end if
> > >	end repeat
> > >end shuffle
> >
> > Hi, Mark.
> >
> > My own attempt at a list randomiser looks like this:
> >
> >   on shuffle(aList)
> >     script o
> >       property l : aList
> >     end script
> >
> >     set lengthMinus1 to (count aList) - 1
> >     repeat with i from 1 to lengthMinus1 + 1
> >       set j to (random number lengthMinus1) + 1
> >       set v to item i of o's l
> >       set item i of o's l to item j of o's l
> >       set item j of o's l to v
> >     end repeat
> >   end shuffle
> >
> > Apart from the fact that it uses AppleScript performance logic
> > (referenced list variable, different random number syntax, not bothering
> > to see if j = i, not setting-by-list), are there any randomness
> > implications in the fact that my item i can be exchanged with any item in
> > the list, whereas yours is only exchanged with items that come in front of
> > it?
> >
> > NG
> >
>
> --
> Sent from Gmail for mobile | mobile.google.com
>
> Mark J. Reed <[log in to unmask]>
>

-- 
Sent from Gmail for mobile | mobile.google.com

Mark J. Reed <[log in to unmask]>