random picks from a list

[Anton Vredegoor]

Manuel Garcia <news at manuelmgarcia.com> wrote:

>Actually, you may not want to do this.  If you pick your numbers from
>a list of 'likely winning' numbers, or even if you try to 'juke' the
>game and pick your numbers from a list of 'unlikely winning' numbers,
>you are competing against people who are trying exactly the same
>strategy, or a similar strategy.  So if you do win, you will be more
>likely to have to share your winnings.
>
>(Not that the problem of 'sharing your lottery winnings' is a very
>common or worrisome problem... ;-)
>
>You can read more about it from The Straight Dope:
>
>http://www.straightdope.com/classics/a4_119.html
>
>Just pick your numbers completely randomly, and the chances of having
>to share lottery winnings will be made as small as possible.  Python's
>random number generator has been 'beefed-up' to the Mersenne Twister
>generator in Python 2.3 (currently in beta), so you can rest assured
>that your random numbers are just as good as anyone else's (except
>professional cryptographers, who get their random numbers from fancy
>hardware).

Well, since it's friday the thirteenth today I didn't want to do this,
but having Python programmers rely on brute force Mersenne Twisting
for choosing lottery numbers could give them a disadvantage.

For example a list of 49 items gives:

608281864034267560872252163321295376887552831379210240000000000

possible permutations, while there's only 53 bit precision floats.
The impressive period of the Mersenne Twister (2**19937-1) should not
distract from the fact that there's not enough floating point bits to
assign a unique floating point number to each of the possible
permutations of this list. In Python23 there seems to be a sample
function but I'm not completely sure that it solves this issue. Does
it call the Twister separately for each item, and if it did would it
make enough of a difference? I'll leave that question to the
mathematicians and floating point specialists.

Maybe this program gives Python programmers a better winning chance
with choosing 6 out of 49 for example, because it first chooses from a
relatively small set of combinations, and next it chooses from an even
smaller number of permutations. 

Anton

#sample.py
from operator import mul
from random import randrange

class combinations:
    
    def __init__(self,n,k):
        self.n,self.k,self.count = n,k,noverk(n,k)
    
    def __getitem__(self,index):
        #combination number index
        if index > self.count - 1: raise IndexError
        res,x,rest = [],self.n,index
        for i in range(self.k,0,-1):
            while noverk(x,i) > rest : x -= 1
            rest -= noverk(x,i)
            res.append(x)
        return res

def indexedperm(L,index):
    m,n = index,len(L)
    res,T = L[:],L[:]
    for i in range(n):
        m,d = divmod(m,n-i)
        res[i] = T.pop(d)
    return res

def fac(n):
    return reduce(mul,range(2,n+1),1L)
        
def noverk(n,k):
    #compute n over k
    return reduce(lambda a,b: a*(n-b)/(b+1),range(k),1)

def sample(population,k):
    n = len(population)
    C = combinations(n,k)
    nc,np = C.count,fac(k)
    c_idx,p_idx = randrange(nc),randrange(np)
    seq = indexedperm(C[c_idx],p_idx)
    return [population[i] for i in seq]
    
def test():
    print sample(range(1,50),6)

if __name__ == '__main__':
    test()