python - "Smart"解决具有多个集合的子集和问题的方法

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]

已经提出了解决此问题的方法 here ，但它是一种蛮力方法；由于在我的情况下集合的数量和它们的大小会大得多，我想要一个与 一起运行的算法最少迭代次数可能的。

你会建议我什么方法？

Answer 1

首先让我们只解决两个集合。这被称为“二和”问题。你有两套 a和 b添加到 l .自 a + b = l我们知道 l - a = b .这很重要，因为我们可以确定 l - a在 b在 O(1) 时间内。而不是循环遍历 b在 O(b) 时间内找到它。这意味着我们可以在 O(a) 时间内解决 2 sum 问题。

备注 :为简洁起见，提供的代码仅产生一种解决方案。然而变化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^⌈s/2⌉) 时间和空间中运行的通用版本。其中 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只是浪费时间和空间。