固定长度整数分区的唯一置换，其中每个元素有一个最大值

Question

这个问题类似于我几个月前的一个问题：Generating a numpy array with all combinations of numbers that sum to less than a given number。 在这个问题中，我想生成所有的数，它们的总和至多是一个常数，因为每个元素都有一定的最大值。在

这一次我要计算所有的排列，它们的总和正好等于这个常数。这可以看作是计算整数分区的唯一排列，其中每个元素都有一定的最大值。最终结果应该存储在numpy数组中。在

使用发电机，一个单一的班轮达到我们想要的：

import numpy as np
from itertools import product
K = 3 
maxRange = np.array([1,3,2]) 

states = np.array([i for i in product(*(range(i+1) for i in maxRange)) if sum(i)==K]) 

给予

^{pr2}$

当K=20和{}时，我的性能相当慢。排列的数量限制在53130个，但已经需要20秒。我的直觉告诉我这应该不到一秒钟。在

有没有更快的解决方案？我很难修改我前面问题的解决方案来解释这个问题，因为我不知道如何切断排列，而这些排列再加起来就不可能是K。在

我不介意使用numba的@jit运算符的解决方案。。。只要他们比我现在的速度快！在

提前谢谢。在

Answer 1

我已经考虑了很长时间，但是我已经设法将这个问题的解决方案修改为Generating a numpy array with all combinations of numbers that sum to less than a given number：

对于分区的数量，我们的想法是计算数组feasible_range，它指定在某个阶段我们至少总共需要多少才能到达max_sum。例如，如果我们想达到3和max_range[0] == 1，那么在开始最后一个元素之前，我们需要至少有2个。此数组从累积和开始：

feasible_range = np.maximum(max_sum - np.append(np.array([0]),np.cumsum(max_range)[:-1]),0)

现在我们可以像以前一样计算分区的数目，方法是将永远不会导致可行分区的元素设置为0。在

^{pr2}$

配分函数也有类似的解释。在

^{3}$

对于K=20和maxRange = [20]*6，partition(maxRange,K)需要13ms，而第一次需要18.5秒。在

我不太喜欢我必须复制的部分；这可能可以通过颠倒顺序来避免。不过，现在的速度已经足够快了。在