number generator

[Anton Vredegoor]

Dick Moores wrote:

> If the added constraint is instead that the probability of generating 
> a given list of length N be the same as that of generating any other 
> list of length N, then I believe my function does the job. Of course, 
> [1,46,1,1,1] and [1,1,46,1,1], as Python lists, are distinct. I ran 
> this test for M == 8 and N == 4:

Yes, I believe your function is OK. But the 'fencepost' method posted 
earlier in this thread also does this and it's faster AND it's only two 
line of code ...

> A = []
> B = []
> for x in range(100000):
>      lst = sumRndInt(8,4)
>      if lst not in A:
>          A.append(lst)
>          B.append(1)
>      else:
>          i = A.index(lst)
>          B[i] += 1
> 
> A.sort()

Doesn't sorting break the correspondence between A and B? Also, a more 
pythonic way to count would be to convert the lst into a tuple and then 
do something with a dictionary. Dictionaries have faster lookup. For 
example:

T = tuple(lst)
D[T] = D.get(T,0) + 1

in the loop in order to count the occurrences.

I'm totally fascinated with this stuff myself so it's a bit hard to 
guess whether someone still is interested, but anyway, here are some 
further explorations involving partitions. The code prints the number of 
distinct permutations for each partition.

from operator import mul

def part(m,n,r):
     L = [0]*n
     while m:
         x =  pn(m-1,n-1)
         if r < x:
             L[n-1] += 1
             m -= 1
             n -= 1
         else:
             for i in range(n):
                 L[i] += 1
             r -= x
             m -= n
     return L

def memoize(fn):
     cache = {}
     def proxy(*args):
         try: return cache[args]
         except KeyError: return cache.setdefault(args, fn(*args))
     return proxy

@memoize
def pn(m,n):
     if m<n or n==0:
         return 0
     if m==n or n==1:
         return 1
     return pn(m-1,n-1)+pn(m-n,n)

@memoize
def fac(n):
     if n == 1:
         return 1
     return n*fac(n-1)

@memoize
def ncomb(n,k):
     return reduce(lambda a,b: a*(n-b)/(b+1),range(k),1)

@memoize
def _np(T):
     if T:
         up = fac(sum(T))
         down = reduce(mul,map(fac,T))
         return up/down
     else:
         return 1

def nperm(L):
     f = dict((x,L.count(x)) for x in set(L))
     return _np(tuple(f.values()))

def test():
     m = 50
     n = 5
     np=pn(m,n)
     total = 0
     for r in xrange(np):
         x = part(m,n,r)
         np = nperm(x)
         total += np
         print np,x
     assert total == ncomb(m-1,n-1)

if __name__=='__main__':
     test()

I posted some easy way of generating all outcomes by index -using a 
combinations function- before in this thread. Using just a single 
randint call one could output a random list of numbers adding up to 
something.

But I think it would be possible to do it with distinct permutations of 
these partitions too. I think I did that in old thread. The only problem 
is that in order to look up which distinct permutation of which 
partition is indexed there should be a way to compute a table containing 
info about how many permutations a certain partition contributes to the 
total. But the code would then also need a distinct permutation by index 
function (I've got one but it's not exactly beautiful) while the code is 
becoming very complex even now without the extra lookup table, compared 
to the simple combinations code.

And compared to the two line fencepost method it's just crazy :-)

But I have a hunch there must be a way to generate such a table without 
actually computing any partitions at all and then one could do some kind 
of 3d bisect to look things up. Maybe in a few years, or sooner if 
someone posts an idea that simplifies things.

A.