Improve this recursive code please!

[Anton Vredegoor]

Steven Taschuk <staschuk at telusplanet.net> wrote:

>Arrange m Os and n-1 |s in a row.  The |s are bin boundaries; the
>Os are bricks.  Example, with eight bricks in four bins:
>    O O O | O | | O O O O
>That's the arrangement (3, 1, 0, 4).
>
>This is equivalent to replacing n-1 of m+n-1 Os with |s, so
>there's m+n-1 choose n-1 ways to do it.  (Note that m+n-1 choose m
>= m+n-1 choose n-1.)

Thanks. This means one could also use the code below. * Warning, wheel
reinvention ahead :-) * This implementation has an advantage over the
generator approach because it indexes a specific arrangement
instantly, without having to go through all the previous arrangements.


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 unique permutation 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 arrangement(m,n,index):
    #return an indexed arrangement of m bricks in n bins
    L = list("0"*m+"1"*(n-1))
    s = "".join(uniquePermute(L,index))
    return map(len,s.split("1"))

def countArrangements(m,n):
    #count the number of arrangements of m bricks in n bins
    def noverk(n,k):
    #compute n over k
        return reduce(lambda a,b: a*(n-b)/(b+1),range(k),1)
    return(noverk(m+n-1,m))

def test():
    bricks, bins = 4,4
    for i in xrange(countArrangements(bricks,bins)):
        print "%3s %15s" %(i,arrangement(bricks,bins,i))
    
if __name__=='__main__':
    test()