Well, let me take another crack at explaining, sticking with the
3-element list example.
There are three possible choices for what the first element gets
swapped with, three for what the second gets swapped with, and three
for the third (where one of the "swaps" in each case is a no-op,
"swapping" an item with itself). That means there are 3 x 3 x 3 = 27
different sequences of swaps your code can make. You can enumerate
them if you like - just write the number of the item swapped with (the
result of the random number call) in each position:
111, 112, 113, 121, 122, 123, etc., all the way up to 333. If you do
that you can count the 27 possibilities.
But: there are only six different possible end results of all that
swapping. So there's no way for each of those swap chains to have a
different outcome. There must be sets of swap sequences where each
sequence gives the same end result even though it gets there by a
different route.
For instance, consider the first sequence, which I listed as "111",
meaning you swap each element in turn with the first. If you start
with "abc" (I'll use strings as my "lists" to save typing lots of
curlies and commas), then after the first swap you still have "abc" -
no change, since you "swapped" the "a" with itself After the second
swap you have "bac", and after the third you have the end result
"cab". So 111 yields "cab". But so does 322: swap the first item with
item 3, giving "cba"; then swap the second item with item 2, staying
"cba", then swap the third item with item 2, giving "cab". If you run
through the other 25 swap chains, you'll find two or three more that
give the same result.
But you don't have to do that to see that the odds among the six
possible outcomes are uneven, simply because 27 is not a multiple of
6. There's no way that each of the 6 possible results can be equally
likely because each of the 27 swap sequences *is* equally likely,
which means that the results with more sequences will turn up more
often.
It's like rolling two dice and adding them together. There are only
11 possible totals (2 through 12), but there are 6x6=36 ways of
getting there. 36 isn't a multiple of 11, so the 11 sums can't all be
equally likely. And they aren't - here's only one way to roll a 2 or
12, but 6 ways to roll a 7. So you're much more likely - six times as
likely, in fact - to roll a 7 than a 1 or a 12, and at least somewhat
more likely to roll a 7 than any other number. Which is why the house
wins money when you play Craps.
Basically, not how many final outcomes there are that determine the
probability. Otherwise the old joke would be true about everything
being a 50/50 shot because either it happens or it doesnt. :). What
matters is how you get there.
On 4/15/08, Nigel Garvey <[log in to unmask]> wrote:
> "Mark J. Reed" wrote on Mon, 14 Apr 2008 09:34:11 -0400:
>
> >On Mon, Apr 14, 2008 at 8:35 AM, Mark J. Reed <[log in to unmask]> wrote:
> >> 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
> >
> >... well, 27, actually, but you get the idea. :)
> >
> >Here are the actual numbers:
> >
> >Sequence: Probability
> >{1, 3, 2}: 5/27
> >{2, 1, 3}: 5/27
> >{2, 3, 1}: 5/27
> >{1, 2, 3}: 4/27
> >{3, 1, 2}: 4/27
> >{3, 2, 1}: 4/27
>
> OK. I'm convinced. I don't know how you arrived at these probabilities
> and the explanation doesn't hang together in my head, but an intensive
> test shows that the 5/27 results do tend to come up slightly more often
> with my script than do the 4/27s; whereas with your script, the spread is
> more even. What's more, adapting my code to your algorithm makes it even
> faster. :)
>
> on shuffle(aList)
> script o
> property l : aList
> end script
>
> repeat with i from (count aList) to 2 by -1
> set j to (random number (i - 1)) + 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
>
>
> NG
>
--
Sent from Gmail for mobile | mobile.google.com
Mark J. Reed <[log in to unmask]>
|
