python - 固定长度整数分区的唯一排列，其中每个元素都有一个最大值

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

给予

array([[0, 1, 2],
       [0, 2, 1],
       [0, 3, 0],
       [1, 0, 2],
       [1, 1, 1],
       [1, 2, 0]])

当 K=20 和 maxRange = [20]*6 时，我的性能非常慢。排列数量限制为 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。

def number_of_partitions(max_range, max_sum):
    M = max_sum + 1
    N = len(max_range) 
    arr = np.zeros(shape=(M,N), dtype = int)    
    feasible_range = max_sum - np.append(np.array([0]),np.cumsum(max_range)[:-1])
    feasible_range = np.maximum(feasible_range,0)     

    arr[:,-1] = np.where(np.arange(M) <= min(max_range[-1], max_sum), 1, 0) 
    arr[:feasible_range[-1],-1] = 0
    for i in range(N-2,-1,-1):
        for j in range(max_range[i]+1):
            arr[j:,i] += arr[:M-j,i+1] 
        arr[:feasible_range[i],i]=0  #Set options that will never add up to max_sum at 0.
    return arr.sum(axis = 0),feasible_range

配分函数也有与之前类似的解释。

def partition(max_range, max_sum, out = None, n_part = None,feasible_range=None):
    #Gives all possible partitions of the sets 0,...,max_range[i] that sum up to  max_sum. 
    if out is None:
        max_range = np.asarray(max_range, dtype = int).ravel()
        n_part,feasible_range = number_of_partitions(max_range, max_sum)
        out = np.zeros(shape = (n_part[0], max_range.size), dtype = int)

    if(max_range.size == 1):
        out[:] = np.arange(feasible_range[0],min(max_range[0],max_sum) + 1, dtype = int).reshape(-1,1)
        return out

    #Copy is needed since otherwise we overwrite some values of P.
    P = partition(max_range[1:], max_sum, out=out[:n_part[1],1:], n_part = n_part[1:],feasible_range=feasible_range[1:]).copy()      


    S = max_sum - P.sum(axis = 1) #The remaining space in the partition 
    offset, sz  = 0, 0
    for i in range(max_range[0]+1):
        #select indices for which there is remaining space
        #do this only if adding i brings us within the feasible_range.
        ind, = np.where(np.logical_and(S-i>=0,S-i <= max_sum-feasible_range[0])) 
        offset, sz = offset + sz, ind.size
        out[offset:offset+sz, 0] = i
        out[offset:offset+sz, 1:] = P[ind]
    return out

对于 K=20 和 maxRange = [20]*6，partition(maxRange,K) 需要 13 毫秒，而之前需要 18.5 秒。

我不太喜欢我必须复制的部分；通过颠倒顺序也许可以避免这种情况。不过现在速度已经足够好了。