高效的项目分级算法(itertools/numpy)

Question

我认为这是一个常见的组合问题,但我似乎无法找到它的名称或任何有关它的材料.我在Python和numpy中这样做,但如果有一个快速矩阵方法,我可以翻译.

基本上,给定n个项目,我需要生成所有方法将它们放入m个箱子中.举个例子,将4个项目合并为3个区域会产生类似的结果[(4, 0, 0), (3, 1, 0), (3, 0, 1), (2, 2, 0), (2, 1, 1), ...].这是一个固定总额的产品.

使用itertools实现这一点非常简单.

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))

不幸的是,我认为在循环中进行后续计算将是低效的.使用它作为2D numpy数组稍后会更快,但我无法找到一种有效的方法来构建一个数组.我可以遍历ifilter结果,构建一个可能性列表,并使用它来构建数组,但这似乎是一个巨大的浪费.

我猜这样做的最好方法是建立一切"笨拙的方式",但我不知道该怎么做.stackoverflow上有一个快速的产品实现:使用numpy构建两个数组的所有组合的数组.我猜你可以修改它只是输出正确总和的产品.数组的大小应该是((m-1)+ n)选择n,因为有m-1个bin边界.

有任何想法吗？基准非常感谢,但不是必需的.

Answer 1

基于递归C(n,k)= C(n-1,k)+ C(n-1,k-1),使用numpy操作进行记忆.

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)

(20,5)的时间(秒):

0.0129251480103