number generator

[Anton Vredegoor]

Terry Reedy wrote:

> Partitioning positive count m into n positive counts that sum to m is a 
> standard combinatorial problem at least 300 years old.  The number of such 
> partitions, P(m,n)  has no known exact formula but can be computed 
> inductively rather easily.  The partitions for m and n can be ranked in 
> lexicographic order from 0 to P(m,n)-1.  Given a rank r in that range, one 
> can calculate the particular partition that has that rank.  So a 
> equi-probable random count in the range can be turned into a equi-probable 
> random partition.

Yes that was one of my first ideas too. But later on Steven pointed out 
that one can view the problem like this:

00010000100010100

That would be [3,4,3,1,2]

where the '1' elements are like dividing shutters that partition the row 
of '0'. This means that the problem is reduced to permutations (albeit 
unique permutations) which are a lot simpler to compute than partitions.

Ok I'll admit that I succeeded in translating my 'Goldberg' solution to 
this case, I can't expect anyone to dust off and read 4 year old threads 
anyway :-)

(by the way I'm still convinced that this code can be simplified a lot)

def starters(L):
     n,np,R = len(L),1,range(len(L))
     bf = [L[:i].count(L[i]) for i in R]
     for i in R: np = np*(n-i)/(bf[i]+1)
     return [(i,np*L[i:].count(L[i])/n) for i in R if not bf[i]]

def perm(index,L):
     remain,n = index,len(L)
     res,T = L[:],L[:]
     for i in range(n):
         for j,k in starters(T):
             if remain-k < 0:
                 res[i] = T.pop(j)
                 break
             remain -= k
     return res

def nperm(L):
     return reduce(lambda a,b:a+b,[k for j,k in starters(L)])

def bb(i,bricks,bins):
     L = [1] * (bins-1) + [0] * (bins-1)
     R = [1]
     for x in perm(i,L):
         if x:  R.append(1)
         else: R[-1]+=1
     return R

def test():
     bricks,bins =  7, 4
     L = [1] * (bins-1) + [0] * (bins-1)
     for i in range(nperm(L)):
         print bb(i,bricks,bins)

if __name__=='__main__':
     test()


> This topic is section 3.1 in Combinatorial Algorithms: Generation, 
> Enumeration, and Search by Kreher and Stinson.  The authors reference 
> several other books as their sources.

Great book!

> I plan to someday rewrite many of their pseudocode algorithms in Python.

That would be my dream job. If only I understood more of them. But I'm 
slowly making progress in other areas so that one day I will maybe 
reread the book and also understand the second half.

A.