假设你有以下一组数字{3,6,10,9,13,16,19},但不一定是按顺序排列的。现在,假设你不知道这是集合{3,6,10}的所有可能组合,是否有一种算法(可以使用任何编程语言),能够高效地找到这些组合呢?
基本上,我想从总集中恢复出列表 - 其中包括所有数字。如果已经有一个有效的算法存在,我不想重复造轮子。
基本上,我想从总集中恢复出列表 - 其中包括所有数字。如果已经有一个有效的算法存在,我不想重复造轮子。
对于一般情况,其中元素数量可达任意数量的情况,下面是一个O(q * log(q))的算法,其中q是输入列表的大小:
以下是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]
1) 找到最小的两个数,它们必须是原始列表的一部分。
2) 找到它们的总和,比列表中更小的所有数字都必须是原始列表的一部分。
3) 找到下一个最小的总和,并重复此过程,直到完成所有两个数字的总和。
每次添加一个数字到原始列表或找到一个总和时,将其从大列表中删除。
4) 继续使用3个数字的总和,并不断增加,直到大列表为空为止。
编辑:
查找下一个最小的总和需要一个已排序的数字列表。如果您的列表是A、B、C、D、E,则最小的总和是A+B,下一个最小的总和是A+C。
性能非常糟糕:2^N,但如果我正确理解了您的问题,列表包含您的原始列表和所有可能的总和,这将允许您大大提高性能。
例如,您知道要查找多少个数字,这意味着您知道仅需要一个数字,而且由于您还知道列表中的最大数字,因此最后一个数字是最大数字减去已添加到原始列表中的所有数字。
这是如何做的。或者至少是一个朴素的解决方案。
首先,按升序排序数字。假设A是排序后的结果列表,S是可以构建A的最小数字集合。
遍历A。当不存在添加到ai的S子集时,添加一个新数字到S,使其满足条件。
在第一次迭代中,这会添加min(A)。第二个数字可能会在S中。这相当于计算密集型,因为你需要确保对于A中检查的每个数字,都存在一个S的子集使其加起来等于它,并且你不会添加一个创建了S的子集并且加起来等于A中某个元素的数字。
可以通过每次向S添加数字时,计算包括该新元素在内的所有可能的总和,并将其从A中删除来优化此过程。继续进行,直到清空A。
如果数字可以为负数,则变得更加复杂,但只要A中有一个负元素,就能看出来。