Subject: | |
From: | |
Reply To: | |
Date: | Mon, 14 Apr 2008 08:30:20 -0400 |
Content-Type: | text/plain |
Parts/Attachments: |
|
|
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]>
|
|
|