Indeed you are correct. The maths is simple (even if not very obvious or
intuitive).
Sorting N lines by random(K)
The likelihood of swapping any two lines *should* be 1/2, but (because
the sort is stable, and because they are random *integers*), there is a
1/K chance of the two random values rounding to the same integer, and
hence the actual probability is (1-1/K)/2 and the probability of not
swapping is (1+1/K)/2
So in Geoff's example (N=2, K=2) gives probabilities of (1-0.5)/2 i.e.
1/4 and 3/4
Changing K to 3 would make a slight improvement - 1/3 and 2/3
at K=4 we get 3/8 and 5/8, etc.
so by the time K=1000
Interestingly, the poor performance for low values of K is completely
independent of N - it's just easier to see it for very small values of N.
If you set N to 5, you want to get an even spread of results, each with
a probability of 8.333/1000
In fact with K=2 you get a range from 0 to 180/1000
So - random() works just fine - but using it correctly is harder than
you might expect. I think it would be worth a feature request to make it
much less likely that the innocent will fall into the many pitfalls.
-- Alex.
On 23/05/2013 20:30, Geoff Canyon wrote:
There is, indeed much confusion here. I, of course, am correct ;-)
I simplified the problem to a list of two items:
1,2
That way the sort command has exactly two outcomes. It either reverses the
list, or it doesn't. The two outcomes should happen roughly 50% of the
time. This script demonstrates that sorting by a large random number works,
and sorting by a random number up to the number of items (2) does not.
on mouseUp
put "1,2" into originalList
repeat 10000
put originalList into newList
sort items of newList by random(2)
if newList is originalList then add 1 to sameCount1
end repeat
repeat 10000
put originalList into newList
sort items of newList by random(999999999)
if newList is originalList then add 1 to sameCount2
end repeat
put "Sorting by random(2) kept the same order" && sameCount1 && "out of
10000 times." & cr & \
"Sorting by random(999999999) kept the same order" && sameCount2
&& "out of 10000 times."
end mouseUp
For anyone interested in the math, as you would expect, the random numbers
for the sort come out 2,1 roughly 1/4 of the time, so the result is that
the list is in the same order roughly 75% of the time when using random(2).
Here's one result I got:
Sorting by random(2) kept the same order 7514 out of 10000 times.
Sorting by random(999999999) kept the same order 5014 out of 10000 times.
If anyone disagrees, come at me, bro. ;-)
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
