有效地找到整数集组合的所有可能总和

Question

我有一个算法可以找到 k 个元组组合的所有唯一总和的集合，这些元组是从元组列表中替换绘制的。每个元组包含 n 个正整数，这些整数的顺序很重要，元组的总和定义为逐元素加法。例如(1, 2, 3) + (4, 5, 6) = (5, 7, 9)

k=2 和 n=3 的简单示例：

input = [(1,0,0), (2,1,1), (3,3,2)]  
solution = [(1,0,0)+(2,1,1), (1,0,0)+(3,3,2), (2,1,1)+(3,3,2), (1,0,0)+(1,0,0), (2,1,1)+(2,1,1), (3,3,2)+(3,3,2)]  
solution = [(3,1,1), (4,3,2), (5,4,3), (2,0,0), (4,2,2), (6,6,2)]

实际上，元组中的整数范围是 0 到 50（在某些位置可能会有更多限制，例如 [0:2]），k 最多有 4 个组合，元组的长度最多为 5 .要提取的元组数量增加到一千个。

我目前拥有的算法是对相关问题中提出的算法的改编，它比使用 itertools 枚举所有组合更有效（如果我们从 1000 个元组中抽取 4 个元组，则有数十亿种组合，但是数量总和将少几个数量级），但我不知道如何将位集应用于这个问题。

# example where length of tuples n = 3:
lst = []
for x in range(0,50,2):
    for y in range(0, 20, 1):
        for z in range(0, 3, 1):
            lst.append((x,y,z))

# this function works for any k and n
def unique_combination_sums(lst, k):
    n = len(lst[0])
    sums = {tuple(0 for _ in range(n))}  # initialize with tuple of zeros
    for _ in range(k):
        sums = {tuple(s[i]+x[i] for i in range(n)) for s in sums for x in lst}
    return sums

unique_combination_sums(lst, 4)

Answer 1

对于这个问题，您当前的实施看起来是正确且有效的。正如您所提到的，应用位集或类似技术可能不会显着提高性能，因为唯一和的数量远小于可能组合的数量。

您可以考虑的一种可能的优化是记忆，它可以减少冗余计算并加速更大输入大小的算法。这是一个示例实现：

def unique_combination_sums(lst, k, memo={}):
    n = len(lst[0])
    if k == 0:
        return {tuple(0 for _ in range(n))}
    if (tuple(map(len, memo.keys())), k) == ((n,)*k, k):
        return memo[(tuple(map(len, memo.keys())), k)]
    sums = {tuple(s[i]+x[i] for i in range(n)) for s in unique_combination_sums(lst, k-1, memo) for x in lst}
    memo[(tuple(map(len, memo.keys())), k)] = sums
    return sums

这个实现添加了一个备忘录字典来存储以前计算的结果。备忘录键是先前计算的集合的长度和 k 的当前值的元组。如果再次使用相同的参数调用该函数，它将返回缓存的结果而不是重新计算它。

您可以尝试在更大的输入尺寸上运行此实现，并将其性能与原始实现进行比较，看看是否有明显的改进。

Answer 2

您实际上可以将元组编码为整数。由于您提到整数范围为

[0, 50]

，并且最多可能有5个这样的整数，因此创建了一个

51^5 = 345,025,251

值的范围，这是完全可行的。

要了解我们如何进行这种编码，请考虑十进制数的工作原理 -

123

表示

1*100 + 2*10 + 1*1

。每个数字乘以基数 (10) 的某个幂，对应于它的位置。每个数字只有一种表示形式，因为每个数字都小于基数 (10) 本身。那时我们可以做类似的事情；我们可以选择一个足够大的基数，比如 100，然后将元组中的每个值乘以该基数的相应幂。举个例子：

(1, 4, 7)
-> 1*100^2 + 4*100^1 + 7*100^0
-> 1*10000 + 4*100   + 7
-> 10407

这项工作本身非常好，但是无论您为整数情况使用什么底层求解器，在较小的数字上都可能表现得更好，所以我们真的应该尽可能地“压缩”表示。这意味着选择尽可能小的基地。实际上，这意味着为混合基数系统选择 多个 基数。无需过多赘述，这意味着如果元组的一个位置仅跨越一小段整数区间，我们将不会“浪费”空间来获取在该特定元组位置永远不存在的值。对于任意示例，这可能是什么样子：

(1, 4, 7, 11)
-> 1*22*7*15 + 4*22*7 + 7*22 + 11*1
-> 2310      + 616    + 154  + 11
-> 3091
// Here we arbitrarily choose the radices [22, 7, 15]
// In practice, we actually choose meaningful (and minimal) radices

此外，我们还可以减去元组位置的最小值，以进一步缩小值。当我们将值转换回元组时，我们只需要记住将适当的偏移量乘以元素数加回去。

综上所述，这是执行此操作的代码：

from functools import wraps


def transform_tuples(func):
    @wraps(func)
    def inner(arr, n):
        if n == 0 or not arr:
            return set()
        
        groups = [(max(g)-min(g), min(g)) for g in zip(*arr)]
        
        def encode(tup):
            val = 0
            for (size, low), elem in zip(groups, tup):
                val *= size * n + 1
                val += elem - low
            return val
            
        def decode(val):
            tup = []
            for size, low in groups[::-1]:
                val, part = divmod(val, size * n + 1)
                tup.append(part + low * n)
            return tuple(tup[::-1])
            
        result = func([encode(tup) for tup in arr], n)
        return [decode(val) for val in result]
    
    return inner

这是一个装饰器——你将它应用到函数中来解决最初的基于整数的问题，它会将函数转换为对元组进行操作的函数。

例如，从上面链接的相关问题中获取

Kelly1

solution，我们可以对其进行装饰，然后它将对元组起作用：

@transform_tuples
def Kelly1(a, n):
    sums = {0}
    for _ in range(n):
        sums = {s + x for s in sums for x in a}
    return sums

在你的例子中调用它：

tuples = [(1,0,0), (2,1,1), (3,3,2)]
k = 2

print(Kelly1(tuples, k))

出品：

[(2, 0, 0), (5, 4, 3), (3, 1, 1), (6, 6, 4), (4, 2, 2), (4, 3, 2)]

所以你可以采用最快的实现，根据需要调整/优化它，然后装饰它以在元组上运行。