python - 用模式划分整数

Question

我知道整数分区的问题很古老，并且这里有很多关于它的问题和答案，但是经过广泛搜索后，我还没有找到我正在寻找的东西。公平地说，我的解决方案并不算太糟糕，但我想知道是否有更快/更好的方法来执行以下操作:

我需要将一个整数划分为一个固定长度的分区，其中可能包含值 0，并且分区中的每个“位置”都受最大可能值的影响。例如:

>>>list(partition(number = 5, max_vals = (1,0,3,4)))
[(1, 0, 3, 1),
 (1, 0, 2, 2),
 (1, 0, 0, 4),
 (1, 0, 1, 3),
 (0, 0, 1, 4),
 (0, 0, 2, 3),
 (0, 0, 3, 2)]

我的解决方案如下:

from collections import Counter
from itertools import combinations

def partition(number:int, max_vals:tuple):
    S = set(combinations((k for i,val in enumerate(max_vals) for k in [i]*val), number))
    for s in S:
        c = Counter(s)
        yield tuple([c[n] for n in range(len(max_vals))])

本质上，我首先为每个插槽创建“ token ”，然后组合正确数量的 token ，最后计算每个插槽有多少个 token 。

我不太喜欢为每个分区实例化一个Counter，但我最不喜欢的是组合生成的元组比需要的多得多然后我用 set() 丢弃所有重复项，这看起来效率很低。有更好的办法吗？

Answer 1

尽管一定有更好的算法、相对更简单、更快的解决方案，使用 itertools.product将是:

>>> from itertools import product
>>> def partition_2(number:int, max_vals:tuple):
        return (comb for comb in 
                product(*(range(min(number, i) + 1) for i in max_vals)) 
                if sum(comb)==number)

>>> list(partition_2(number = 5, max_vals = (1,0,3,4)))
[(0, 0, 1, 4),
 (0, 0, 2, 3),
 (0, 0, 3, 2),
 (1, 0, 0, 4),
 (1, 0, 1, 3),
 (1, 0, 2, 2),
 (1, 0, 3, 1)]

性能:

>>> %timeit list(partition(number = 15, max_vals = (1,0,3,4)*3))
155 ms ± 681 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>> %timeit list(partition_2(number = 15, max_vals = (1,0,3,4)*3))
14.7 ms ± 763 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
################################################################################
>>> %timeit list(partition(number = 5, max_vals = (10,20,30,10,10)))
1.17 s ± 26.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>> %timeit list(partition_2(number = 5, max_vals = (10,20,30,10,10)))
1.21 ms ± 28.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
#################################################################################
>>> %timeit list(partition_2(number = 35, max_vals = (8,9,10,11,12)))
23.2 ms ± 697 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>> %timeit list(partition(number = 35, max_vals = (8,9,10,11,12)))
# Will update when/if it finishes :)