"聪明 "的方法解决多组子集和的问题

Question

我有一定数量的集合，每个集合都包含了数量不等的唯一数字--在它们所属的集合中是唯一的，在其他集合中找不到。

我想做一个最好用Python实现的算法--但也可以是任何其他语言--从这些集合中的每一个集合中找到一个数字组合，并将其相加为一个指定的数字，如果这样做有帮助的话，我知道同一个集合可以有多次，而且一个集合中的元素可以重复使用。

实际例子：比如说我有以下几个集合。

A = {1, 3, 6, 7, 15}
B = {2, 8, 10}
C = {4, 5, 9, 11, 12}

我想用一个方法获得一个数字组合 find_subset_combination(expected_sum, subset_list)

>>> find_subset_combination(41, [A, B, B, C, B])
[1, 8, 10, 12, 10]

已经有人提出了解决这个问题的办法 此处然而，这是一种蛮力的方法；由于在我的情况下，集合的数量和大小都会大得多，我希望有一种算法能用以下方法来运行。迭代次数最少 可能的。

你会建议我用什么方法？

Answer 1

首先让我们只解决两个集合的问题。这就是所谓的 "两组相加 "问题。你有两个集合 a 和 b 增添 l. 由于 a + b = l 我们知道 l - a = b. 这一点很重要，因为我们可以确定 l - a 是在 b 在O(1)时间内完成。而不是循环浏览 b 以在O(b)时间内找到它。这意味着我们可以在O(a)时间内解决2和问题。

注意，我们可以在O(a)时间内解决2和问题。: 为简洁起见，所提供的代码只产生一种解决方案。然而，改变 two_sum 的生成函数可以将它们全部返回。

def two_sum(l, a, b):
    for i in a:
        if l - i in b:
            return i, l - i
    raise ValueError('No solution found')

接下来我们可以解决 "四和 "问题。这次我们有四组 c, d, e 和 f. 通过结合 c 和 d 变成 a和 e 和 f 变成 b 我们可以用 two_sum 以在O(cd + ef)空间和时间内解决问题。要组合这些集合，我们可以使用卡提斯积，将结果加在一起。

请注意: 为了得到所有结果，对所有结果进行卡提斯乘法。a[i] 和 b[j].

import itertools


def combine(*sets):
    result = {}
    for keys in itertools.product(*sets):
        results.setdefault(sum(keys), []).append(keys)
    return results


def four_sum(l, c, d, e, f):
    a = combine(c, d)
    b = combine(e, f)
    i, j = two_sum(l, a, b)
    return (*a[i][0], *b[j][0])

很明显，"三和 "问题只是 "四和 "问题的简化版。不同的是，我们得到的是 a 而不是被要求计算。这在O(a + ef)时间和O(ef)空间内运行。

def three_sum(l, a, e, f):
    b = combine(e, f)
    i, j = two_sum(l, a, b)
    return (i, *b[j][0])

现在我们有足够的信息来解决 "六和 "问题。问题的关键在于我们如何划分所有这些集合？

• 如果我们决定将它们配对在一起，那么我们可以使用'三和'解决方案来获得我们想要的东西。但是，如果我们决定将它们配对在一起，那么我们就可以使用 "三和 "方案来获得我们想要的东西。 这可能不会在最佳时间内运行，因为它的运行时间是 O(ab + bcde)，如果它们都是相同大小，则是 O(n^4)时间。
• 如果我们决定将它们放在三组中，那么我们就可以使用 "二和 "来获得我们想要的东西。这需要O(abc + def)的时间，如果它们的大小都一样，则需要O(n^3)的时间。

在这一点上，我们应该有所有的信息来制作一个通用的版本，在O(n^⌈s2⌉)时间和空间中运行。其中s是输入函数的集合量。

def n_sum(l, *sets):
    midpoint = len(sets) // 2
    a = combine(*sets[:midpoint])
    b = combine(*sets[midpoint:])
    i, j = two_sum(l, a, b)
    return (*a[i][0], *b[j][0])

你可以进一步优化代码。两边之和的大小相当重要。

• 为了说明这一点，你可以想象一边是4组1个数，另一边是4组1000个数。这将在O(1^4 + 1000^4)时间内运行。这显然是 真的 不好。反而可以平衡两边的两个和，使之小很多。通过方程两边有2组1个数和2组1000个数，性能就会增加，O(1^2×1000^2+1^2×1000^2)或者干脆就是O(1000^2)。这远远小于O(1000^4)。

• 在前面的基础上扩展，如果你有3组1000的数字和3组10的数字，那么最好的解决办法就是把两个1000放在一边，其他的都放在另一边。

  • 1000^2 + 10^3×1000 = 2_000_000
  • 交错排序，两边大小相同（10，1000，10），（1000，10，1000）10^2×1000+10×1000^2=10_100_000。

此外，如果提供的每一个集合的数量是均等的，那么你可以通过只调用 combine 一次。例如，如果输入的是 n_sum(l, a, b, c, a, b, c) (没有进行上述优化)，很明显，第二个对 combine 只不过是在浪费时间和空间。