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