我认为这是一个常见的组合问题,但我似乎无法找到它的名称或任何有关它的材料.我在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边界.
有任何想法吗？基准非常感谢,但不是必需的.