[FIXED] Efficient item binning algorithm (itertools/numpy)

Issue

I think this is a common combinatorics problem, but I can't seem to find a name for it or any material about it. I am doing this in Python and numpy, but if there is a fast matrix method for this, I can probably translate.

Basically, given n items, I need to generate all ways to put them in m bins. As an example, binning 4 items into 3 bins would give something like [(4, 0, 0), (3, 1, 0), (3, 0, 1), (2, 2, 0), (2, 1, 1), ...]. This is a product with a fixed total.

Implementing this with itertools is straightforward.

import itertools

def fixed_total_product(bins, num_items):
""" Return iterator of all item binning possibilities. """
return itertools.ifilter(lambda combo: sum(combo) == num_items,
                         itertools.product(xrange(num_items + 1), repeat=bins))

Unfortunately, I think doing subsequent calculations in loops will be inefficient. Working with this as a 2D numpy array would be faster later on, but I can't figure out an efficient way to build an array with this. I could iterate over the ifilter result, building a list of the possibilities, and use this to construct the array, but that seems like a huge waste.

I'm guessing the best way to do this is to build everything "the numpy way", but I'm not sure how to do this. There is a speedy product implementation on stackoverflow: Using numpy to build an array of all combinations of two arrays. I'm guessing you can modify this only to output products with the right sum. The size of the array should be ((m-1) + n) choose n, since there are m-1 bin boundaries.

Any ideas? Benchmarks much appreciated, but not required.

Solution

Based on the recursion C(n, k) = C(n - 1, k) + C(n - 1, k - 1), memoized, using numpy operations.

import numpy as np

def binnings(n, k, cache={}):
    if n == 0:
        return np.zeros((1, k))
    if k == 0:
        return np.empty((0, 0))
    args = (n, k)
    if args in cache:
        return cache[args]
    a = binnings(n - 1, k, cache)
    a1 = a + (np.arange(k) == 0)
    b = binnings(n, k - 1, cache)
    b1 = np.hstack((np.zeros((b.shape[0], 1)), b))
    result = np.vstack((a1, b1))
    cache[args] = result
    return result

if __name__ == '__main__':
    import timeit
    print timeit.timeit('binnings(20, 5, {})', setup='from __main__ import binnings', number=1)

Time in seconds for (20, 5):

0.0129251480103

Answered By - bar