randomly order a list

[Alex Tweedly]

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