Improve this recursive code please!

[Anton Vredegoor]

"Sean Ross" <frobozz_electric at hotmail.com> wrote:

>I've been thinking about this problem for several days. Unfortunately, I
>haven't found a solution for you, but I have found the form of a solution
>that perhaps someone else here will know how to implement:
>
>for arrangement in xuniquepermute(xdistribute(items, bins)):
>    print arrangement  # or perform some other operations with this
>arrangement

Yes, I have been thinking about this too and I've even posted a crude
solution following this line of reasoning. However, before going on I
must point out that there's already a better way to do it (this
generates the arrangements in sorted order):

#an edited version of Steven Taschuk's solution

def findarrangements(bricksleft, binsleft, bins = []):
    if binsleft > 1:
        # More than one bin left, and we need to distribute
        # bricksleft bricks among them.
        for n in range(bricksleft+1):
            # Find arrangements in which next bin has n bricks.
            bins.append(n)
            for x in findarrangements(bricksleft-n, binsleft-1, bins):
                yield x
            bins.pop()
    else:
        # Only one bin left; put all remaining bricks there.
        bins.append(bricksleft) 
        yield bins
        bins.pop()
        
def test():
    for x in findarrangements(4,4):
        print x

if __name__=='__main__':
    test()


>I haven't been able to implement either xdistribute() or xuniquepermute()
>myself, although I will keep trying because I think the idea is sound and
>would work as a solution to your problem. I would be relieved to see an
>implementation of this, as it's become something of an itch for me.

Since it's requested I'll share my recent explorations. I've even
started a separate thread where I'am asking info about turning
recursive functions into generators to enable this solution. It now
also involves conjugating partitions in order to generate only those
partitions that consist of no more parts than the number of bins. I'm
still working on producing indexed partitions instead of generated
ones. The unique permutes are already generated by index. Premature
optimizations won't stop this coder :-P

Anton


def starters(L):
    #return a list of 2-tuples containing info about list 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)
    for i in R:
        if not bf[i]:
            yield i,np*L[i:].count(L[i])/n
    
def uniquepermute(L,index=0):
    #return an uniquepermute of list L
    remain, res, T = index, [], L[:]
    while T:
        for j,k in starters(T):
            if remain-k < 0:
                res.append(T.pop(j))
                break
            remain -= k
    return res

def nperm(L):
    #return the number of possible uniquepermutes of list 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 np

def conjPartition(a):
    #conjugate a partition
    n,b = len(a),[1]*a[0]
    for j in range(1,n):
        for i in range(a[j]):
            b[i]+=1
    return b

def genPartitions(m,n):
    #generate all partitions of m into n parts
    a = [n]*m
    def recPartition(m,B,N):
        #recursive partition function
            if m == 0:
                yield conjPartition(a[:N])
            else:
                for i in range(1,min(B,m)+1):
                    a[N]=i
                    for p in recPartition(m-i,i,N+1): yield p
    for p in recPartition(m-n,n,1): yield p

def findArrangements(m,n):
    #generate all arrangements of m into n 
    pad = [0] *(n-1)
    for i in range(1,n+1):
        for p in genPartitions(m,i):
            b = p + pad
            for j in range(nperm(b)):
                yield uniquepermute(b,j)
        pad = pad[0:-1]

def test():
    for x in findArrangements(4,4):
        print x

if __name__=='__main__':
    test()