Improve this recursive code please!

[Steven Taschuk]

Quoth waxmop:
> Hi - I wrote a program that gets two arguments: numbricks, and numbins.
> The program calculates every possible way to distribute all the bricks
> into the bins, using a recursive function.
  [...]

On further reflection I realized that no recursion is necessary in
the first place:

    def arrangements(bricks, bins):
        """Iterate over arrangements of so many bricks in so many bins."""
        if bricks < 0:
            raise ValueError('bricks == %r < 0' % bricks)
        if bins <= 0:
            raise ValueError('bins == %r <= 0' % bins)
        built = [0]*bins
        built[0] = bricks
        while True:
            yield tuple(built)
            # Change (..., m,   ...bunch of 0s...,   n)     (where m > 0)
            # into   (..., m-1, n+1, ...bunch of 0s...)
            for i in range(bins-2, -1, -1):
                if built[i]:            # built[i] == m
                    break
            else:
                break
            built[i] -= 1
            # following three-step waltz needed lest i+1 == bins-1
            n = built[-1]
            built[-1] = 0
            built[i+1] = n + 1

Admittedly this is more cryptic than a recursive solution.  But it
does have all the other desired properties: it considers each bin
distinct but all bricks the same; it produces results in sorted
order; it holds only one result in memory at a time, avoiding a
combinatoric explosion of memory consumption; and, as an added
benefit, it doesn't recurse at all.  (In a sense, the list of bins
itself serves as the stack.)

It also happens to be easily translated into C, which in this case
produces a considerable performance improvement.  (Among (bricks,
bins) values in [1,8]^2, from 4x to 12x faster on my machine, with
indications that the disparity would be greater for greater
values.)

-- 
Steven Taschuk             "The world will end if you get this wrong."
staschuk at telusplanet.net     -- "Typesetting Mathematics -- User's Guide",
                                 Brian Kernighan and Lorrinda Cherry