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