number generator

[Anton Vredegoor]

Dick Moores wrote:

> Paul Rubin's fencepost method is about 14 times faster than mine for
> the same M == 8 and N == 4!  :(

Actually they looked a bit similar after I had mucked a bit with them 
:-) But indeed it's slow.

> Sorry, I don't understand this. Could you spell it out for me by 
> rewriting my above test to use it? Thanks!

OK here you go. I'm copying a modification from something that I used to 
check something else, I hope you recognize the code after my refactoring.

from itertools import islice
import random

def sumRndInt(m,n):
      while 1:
          L = [random.randint(1,m-n+1) for i in xrange(n)]
          if sum(L) == m:
              yield tuple(L)

def fencepost(m,n):
     while 1:
         t = sorted(random.sample(xrange(1,m), n-1))
         yield tuple((j-i) for i,j in zip([0]+t, t+[m]))

def freq(g,k):
     D = {}
     for x in islice(g,k):
         D[x] = D.get(x,0)+1
     return D

def test():
     m = 7
     n = 4
     k = 20000
     R = freq(sumRndInt(m,n),k)
     F = freq(fencepost(m,n),k)
     assert sorted(R) == sorted(F)
     for x in sorted(R):
         print x,R[x],F[x]

if __name__=='__main__':
     test()