randomly order a list

[Dar Scott]

I did a math.  

The probability of the first element not moving for a k item list named myList that is sorted by

   sort items of myList by random( the number of items of myList )

is p(k) where

p(k) = sum with i from 1 to k of 1/k  *  ( i/k ) ^ (k-1)

That power increasing with k tends to make numbers less than one smaller, but 1 stays the same, so p(k) approaches 1/k as k goes up since (k+1-i)/k is 1 for only i=1.  

This essentially looks at the probability of the first element not moving for each case of its assignment by random (the sum) and each of those depends on the rest of the assignments being the same or higher.  

That seems to work for 1, 2 and 3.  

(This hasn't been blessed by Geoff yet, so don't file this as True, yet.)

Dar




On May 23, 2013, at 2:43 PM, Alex Tweedly wrote:

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