randomly order a list
Alex Tweedly
alex at tweedly.net
Thu May 23 16:43:25 EDT 2013
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 at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode
More information about the use-livecode
mailing list