从数字列表中找到一对和的算法？

Question

从数字列表中找到一对和的算法？

algorithmlanguage-agnostic

11

假设你有以下一组数字{3,6,10,9,13,16,19}，但不一定是按顺序排列的。现在，假设你不知道这是集合{3,6,10}的所有可能组合，是否有一种算法（可以使用任何编程语言），能够高效地找到这些组合呢？

基本上，我想从总集中恢复出列表 - 其中包括所有数字。如果已经有一个有效的算法存在，我不想重复造轮子。

- Programmer

什么使得3、6和10成为这个问题的解决方案？ - Billy ONeal

1

听起来是一个有趣的问题。更正式地说：给定一个包含N个整数的集合S，不一定是有序的，判断集合S中的每个元素是否是集合U中整数的可加组合。听上去对吗？让我想起了子集和问题。（一个NP完全问题） - GManNickG

@Billy, 这三个数字可以用来求解列表中的所有其他数字之和，而且它们互相之间不是彼此的和。我相信解决方案是问题的子集。 - David Kanarek

我只是用这三个数字作为一个例子。基础集合可以是4、5或6个元素。然而，总数始终为2^n-1/。我正在开发一款将安装在微控制器流量传感器上的软件，并且我需要一个高效的算法。 - Programmer

4

如果这个集合是{1,2,3}，那么列表是否会是{1,2,3,3,4,5,6}呢？换句话说，输入的列表中可以有重复元素吗？ - Mark Byers

我想澄清这个问题。将第一个列表（包含所有未排序数字的那个）称为S，第二个子集称为U。你知道其中哪一个，并且你正在尝试找到另一个吗？我猜你有S并想找到U，这正确吗？ - GManNickG

3个回答

4

1) 找到最小的两个数，它们必须是原始列表的一部分。

2) 找到它们的总和，比列表中更小的所有数字都必须是原始列表的一部分。

3) 找到下一个最小的总和，并重复此过程，直到完成所有两个数字的总和。

每次添加一个数字到原始列表或找到一个总和时，将其从大列表中删除。

4) 继续使用3个数字的总和，并不断增加，直到大列表为空为止。

编辑：

查找下一个最小的总和需要一个已排序的数字列表。如果您的列表是A、B、C、D、E，则最小的总和是A+B，下一个最小的总和是A+C。

性能非常糟糕：2^N，但如果我正确理解了您的问题，列表包含您的原始列表和所有可能的总和，这将允许您大大提高性能。

例如，您知道要查找多少个数字，这意味着您知道仅需要一个数字，而且由于您还知道列表中的最大数字，因此最后一个数字是最大数字减去已添加到原始列表中的所有数字。

- David Kanarek

我不确定这是如何工作的...您能详细解释第三步吗？您如何找到下一个最小的总和？ - Mark Byers

这个算法在O(n)符号表示下的性能如何？ - Mark Byers

0

这是如何做的。或者至少是一个朴素的解决方案。

首先，按升序排序数字。假设A是排序后的结果列表，S是可以构建A的最小数字集合。

遍历A。当不存在添加到a_i的S子集时，添加一个新数字到S，使其满足条件。

在第一次迭代中，这会添加min(A)。第二个数字可能会在S中。这相当于计算密集型，因为你需要确保对于A中检查的每个数字，都存在一个S的子集使其加起来等于它，并且你不会添加一个创建了S的子集并且加起来等于A中某个元素的数字。

可以通过每次向S添加数字时，计算包括该新元素在内的所有可能的总和，并将其从A中删除来优化此过程。继续进行，直到清空A。

如果数字可以为负数，则变得更加复杂，但只要A中有一个负元素，就能看出来。

- cletus

天真地说，如果S的大小为n，则必须检查2 ** n个可能的总和，以查看某个子集的数字是否是其总和。但是，您可以大大优化此过程。 - President James K. Polk

你应该在你的cforcoding网站上更新你的stackoverflow徽章。它已经过时了，它说你只有80k个金徽章，而实际上你有276k个！ - Ogen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Byers · Accepted Answer

对于一般情况，其中元素数量可达任意数量的情况，下面是一个O(q * log(q))的算法，其中q是输入列表的大小：

将列表q按升序排序。
删除最小的元素m，并将其添加到结果集中。从q中删除它。
遍历q。保持一个我们已经看到的数字列表。如果我们看到一个数字（与m无关的数字），那么就将其丢弃，因为这个数字是（我们已经看到的数字+m）。这应该保留一半的数字。
重复从步骤2开始，直到找到所有数字。

以下是Python中此算法的实现：

def solve(q):
    q = sorted(q)
    x = []
    while q:
        x.append(q[0])

        s = [False]*len(q)
        s[0] = True
        j = 1

        for i in range(1, len(q)):
            if q[i] == q[0] + q[j]:
                s[i] = True
                j += 1
                while j < len(q) and s[j]:
                    j += 1

        q = [k for k, v in zip(q, s) if not v]
    return x

s = [1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99]
from itertools import combinations
q = list(sum(x) for r in range(1, len(s) + 1) for x in combinations(s, r))
print(solve(q))

结果：

[1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99]

假设列表中仅有3个数字，且没有负数：其中两个数字必须是列表中最小的两个数字。最大的数字必须是所有三个数字的和。通过减法可以找到第三个数字。