我认为这是一个常见的组合数学问题,但我似乎找不到它的名称或任何有关它的材料。我正在用Python和numpy做这件事,但如果有一个快速的矩阵方法,我可能可以翻译。
基本上,给定 n 个项目,我需要生成所有将它们放入 m 个bin的方法。例如,将4个项目放入3个bin将得到类似[(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结果,构建一个可能性列表,并使用它来构建数组,但这似乎是一个巨大的浪费。
我猜最好的方法是用“numpy方式”构建所有东西,但我不确定如何做到这一点。在stackoverflow上有一个快速的产品实现:Using numpy to build an array of all combinations of two arrays。我猜你只能修改它以输出正确和的产品。数组的大小应该是((m-1)+ n)choose n,因为有m-1个bin边界。
有什么想法吗?基准非常赞赏,但不是必需的。
3条答案
按热度按时间cgh8pdjw1#
基于递归C(n,k)= C(n - 1,k)+ C(n - 1,k - 1),记忆化,使用numpy操作。
字符串
(20,5)的时间(秒):
型
xytpbqjk2#
在numpy中使用一些不同的技巧可能会有更快的方法。
numpy.indices
是你想要开始的地方。一旦你将它与rollaxis
合并结合起来,它本质上相当于itertools.product
。Sven Marnach的答案in this question是一个很好的例子(在他的最后一个例子中有一个小错误,但是,这是你想要使用的。它应该是numpy.indices((len(some_list) + 1), * some_length...
)然而,对于这样的东西,使用itertools可能会更具可读性。
numpy.fromiter
比显式转换为列表要快一些,特别是当你给予迭代器中元素的数量时。主要的优点是它使用的内存少得多,这在大迭代器的情况下非常有用。下面是一些使用
numpy.indices
技巧和各种将迭代器转换为numpy数组的方法的例子:字符串
至于时间:
型
你会注意到它们都不是特别快。
您使用的是蛮力算法(生成所有可能的组合,然后过滤它们),我只是在这里的基于numpy的示例中复制它。
可能有一个更有效的方法来做到这一点!然而,我不是一个CS或数学的人无论如何,所以我不知道是否有一个众所周知的算法来做到这一点,而不是首先生成所有可能的组合.
祝你好运,无论如何!
cbwuti443#
我知道我在这里恢复了一个很老的线程,但我希望一个好的解决方案仍然会受到赞赏(即使不再是OP)。
这个问题本身类似于在代码中表示多变量多项式。例如(对应于3个bin中的4个项目的例子),你从扩展
(x+y+z)^4
得到的多项式类似于x^4*y^0*z^0 + 4*x^3*y^1*z^0 + ...
,x,y和z的指数是数组的元素:字符串
如果你仔细观察,你会看到例如
3
右边的元素是(y+z)^1
的指数,2
右边的元素是(y+z)^2
的指数等等。更一般地,在p
右边你有(y+z)^(4-p)
的指数。这表明了一些递归结构:假设e(m,p)表示m
变量的指数(= bin)和p
总指数(=items),然后通过从0
到p
中选择第一个指数q
来获得所有指数,剩余的m-1
变量的指数由e(m-1,p-q)
给出。在
python
和numpy
中,您可以像这样公式化:型
当然,您可以通过预先计算数组大小并直接填充值来提高效率。
如果您需要将
p
项分配到m
bin中,而不是精确地分配,那么您可以使用以下类似的代码。型