Re: number generator

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.
.

Relevant Pages

  • Re: number generator
    ... 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. ... def part: ... But I think it would be possible to do it with distinct permutations of these partitions too. ...
    (comp.lang.python)
  • Re: sums break up
    ... This method works, but if I try to use it with 6, it "forgets" the sum ... def partition_generator: ... # dictionary of unique partitions needed to ... # convert list to tuple (required for dictionary key) ...
    (sci.math)
  • how can I make this script shorter?
    ... I have a script which I use to find all duplicates of files within a ... # return a list of lists of duplicates ... assert(reduce(operator.add, map(len, partitions), 0) ... def enumerateMatches: ...
    (comp.lang.python)
  • Re: Feedback on Sets, and Partitions
    ... David Eppstein wrote: ... I need to generate partitions of sets up to size ... with PEP 318... ... def factorial: ...
    (comp.lang.python)
  • Combinatorics question: shelving books
    ... Twenty different books are to be put on five book shelves, ... How many different arrangements are there if you care about ... order, partition them into 5 partitions, then fill the book shelves ...
    (sci.math)