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. -- http://mail.python.org/mailman/listinfo/python-list