number generator

Anton Vredegoor anton.vredegoor at gmail.com
Sun Mar 11 04:55:33 CET 2007


Terry Reedy wrote:

> "Anton Vredegoor" <anton.vredegoor at gmail.com> wrote in message 
> | 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
> 
> If any of the 1s appear at the ends or together, then you would have 0s in 
> the partition, which is not allowed, as I understood the spec.

Yes, I was writing about the bricks and bins problem from 4 years ago 
which is very similar.

> | unique permutations) which are a lot simpler to compute than partitions.
> 
> I think the simplicity is actually about the same.

Probably yes. It's like the difference between Pascal's triangle and the 
partition numbers' triangle. Anyway, Paul Rubin's idea in this same 
thread stimulated me to simplify my code a lot. It's rather late here so 
I hope I haven't slipped up again.

def comb(i,n,k):
     for j in range(k,0,-1):
         while noverk(n,j) > i :
              n -= 1
         i -= noverk(n,j)
         yield n

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

def bb(i,bricks,bins):
     L = [j+1 for j in comb(i,bricks,bins-1)]
     return [(i-j) for i,j in zip([bricks]+L,L+[0])]

def test():
     bricks, bins = 6,4
     n = noverk(bricks-1,bins-1)
     for i in range(n):
         print bb(i,bricks,bins)

if __name__=='__main__':
     test()

A.




More information about the Python-list mailing list