高效地找出整数集合的所有可能组合之和

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

实际上元组中的整数范围从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)

- jonas87

---

有一个打字错误：在“solution”中，最后的总和是(6,6,4)而不是(6,6,2)。 - Luca Anzalone

你给出的第二个例子只是将range生成的列表组合而已。这只是一个例子吗？还是实际对象也是由range生成的？ - ken

@ken 第二个例子是我用三个嵌套的 range 生成的，只是为了用人造但有点逼真的数据填充 lst 来测试 unique_combination_sums 函数。实际对象不是由 range 生成的，但我们可以假设是在0到50之间的随机整数。 - jonas87

Answer 1

实际上，您可以将元组编码为整数。由于您提到整数范围为[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)]

所以你可以选择最快的实现方式，根据自己的喜好进行调整和优化，然后将其装饰成适用于元组的形式。

- Dillon Davis

---

太棒了，这个代码在我的数据上比我原来发布的代码快了500倍。 - jonas87