高效地获取已排序列表的排序求和

Question

您有一个升序数字列表，您能想到的获取该列表中每两个数字之和的升序列表的最有效算法是什么？结果列表中的重复项无关紧要，如果需要可以删除或避免它们。

要明确一点，我对算法感兴趣。可以自由使用任何语言和范式发布代码。

- Peter Burns

Answer 1

截至2018年修改：你应该停止阅读这篇文章。（但我不能删除它，因为它已经被接受。）

如果你像这样写出总和：

1 4  5  6  8  9
---------------
2 5  6  7  9 10
  8  9 10 12 13
    10 11 13 14
       12 14 15
          16 17
             18

注意到M[i,j] <= M[i,j+1]且M[i,j] <= M[i+1,j]，因此您只需要检查左上角并选择最小值。

例如：

• 只有一个左上角2，选择2
• 只有一个左上角5，选择5
• 6或8，选择6
• 7或8，选择7
• 9或8，选择8
• 9或9，选择两个 :)
• 10或10或10，选择全部
• 12或11，选择11
• 12或12，选择两个
• 13或13，选择两个
• 14或14，选择两个
• 15或16，选择15
• 只有一个左上角16，选择16
• 只有一个左上角17，选择17
• 只有一个左上角18，选择18

当您有很多左上角时，这种解决方案会退化。

我非常确定这个问题是Ω(n²)，因为您必须为每个M[i,j]计算总和--除非有人有更好的求和算法：）

- Porges

---

我认为这是O(n^3)，因为每个阶段都有n个潜在的“左上角”。 - user97370

你可以通过在优先队列中存储每行中第一个未选择的条目来在O(n^2 log n)时间内实现此算法，但从渐近意义上讲，这并不比生成所有和并排序更好。 - Reid Barton

如果您有两个列表而不是一个，长度分别为m和n，其中m<n，则基于k路合并的方法会给出O(mn log m)而不是O(mn log(mn))。此外，如果m相当小（我猜最多只有几百个元素），基于合并的方法将更好地利用处理器缓存（因为优先队列或合并树将适合L1缓存），这可以轻松提高速度100倍或更多，如果编写得非常仔细，还可以很好地利用处理器流水线，这样它应该真的很快。 - dfeuer

回顾四年后，这似乎是一个非常糟糕的归并排序版本 :) - porges

Answer 2

我觉得不需要编写代码，而是用伪代码逐步解释我的逻辑，这样更好的程序员可以在必要时指出我的逻辑漏洞。

第一步，我们从一个长度为n的数字列表开始。对于每个数字，我们需要创建一个长度为n-1的列表，因为我们不会将一个数字加到它自己上面。最终，我们生成了大约n个排序列表，用了O（n^2）的时间。

step 1 (startinglist) 
for each number num1 in startinglist
   for each number num2 in startinglist
      add num1 plus num2 into templist
   add templist to sumlist
return sumlist 

在第二步中，由于列表是按设计排序的（向已排序列表中的每个元素添加一个数字，列表仍将保持排序），因此我们可以通过合并每个列表来执行归并排序，而不是对整个列表进行归并排序。最终，这应该需要O(n^2)时间。

step 2 (sumlist) 
create an empty list mergedlist
for each list templist in sumlist
   set mergelist equal to: merge(mergedlist,templist)
return mergedlist

合并方法将是正常的合并步骤，但需要检查是否存在重复的总和。我不会详细说明，因为任何人都可以查找归并排序。

这就是我的解决方案。整个算法的时间复杂度为O(n^2)。如有错误或改进之处，请随时指出。

- Holtorf

---

我认为这是O(N^3)，因为在第二步中每个阶段都有n次比较。 - user97370

Answer 3

您可以使用Python中的两行代码来完成此操作。

allSums = set(a+b for a in X for b in X)
allSums = sorted(allSums)

这个的成本是n^2（可能还有一个对于集合的额外对数因子？）用于迭代和s * log（s）用于排序，其中s是集合的大小。

例如，如果X = [1,2,4,...,2^n]，那么集合的大小可能会达到n*(n-1)/2。因此，如果您想生成此列表，则最坏情况下至少需要n^2/2，因为这是输出的大小。

但是，如果您要选择结果的前k个元素，则可以使用Frederickson和Johnson的排序X+Y矩阵的选择算法在O（kn）内完成（有关详细信息，请参见这里)。尽管可能可以通过重复使用计算并获得此集合的高效生成器来修改它们以在线生成。

@deuseldorf，Peter (n!)存在一些混淆，我严重怀疑deuseldorf的意思不是“n阶乘”，而只是“n，（非常兴奋）！”

- Pall Melsted

---

这个解决方案的复杂度比其他所有解决方案都要好，我认为是O(n^2.log(n))。它也是最易读和最短的。 - user97370

Answer 4

我能想到的最好的方法是生成每个对之和的矩阵，然后将行合并，就像归并排序一样。我感觉自己缺少一些简单的见解，可以揭示出更高效的解决方案。

我的算法，使用 Haskell 编写：

matrixOfSums list = [[a+b | b <- list, b >= a] | a <- list]

sortedSums = foldl merge [] matrixOfSums

--A normal merge, save that we remove duplicates
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = case compare x y of
    LT -> x:(merge xs (y:ys))
    EQ -> x:(merge xs (dropWhile (==x) ys))
    GT -> y:(merge (x:xs) ys)

我发现了一个小改进，更适合于惰性流式编程。不要一对一对地合并列，而是一次性合并所有列。优点是您可以立即开始获取列表的元素。

-- wide-merge does a standard merge (ala merge-sort) across an arbitrary number of lists
-- wideNubMerge does this while eliminating duplicates
wideNubMerge :: Ord a => [[a]] -> [a]
wideNubMerge ls = wideNubMerge1 $ filter (/= []) ls
wideNubMerge1 [] = []
wideNubMerge1 ls = mini:(wideNubMerge rest)
    where mini = minimum $ map head ls
          rest = map (dropWhile (== mini)) ls

betterSortedSums = wideNubMerge matrixOfSums

然而，如果你知道你将使用所有的总和，并且提前获取其中一些没有优势，那么选择 'foldl merge []'，因为它更快。

- Peter Burns

---

我认为（我的Haskell有点生疏）这是O（N^3），因为对于结果中的每个元素，都要进行O（n）次比较。 - user97370

Answer 5

在SQL中：

create table numbers(n int not null)
insert into numbers(n) values(1),(1), (2), (2), (3), (4)


select distinct num1.n+num2.n sum2n
from numbers num1
inner join numbers num2 
    on num1.n<>num2.n
order by sum2n

C# LINQ：

List<int> num = new List<int>{ 1, 1, 2, 2, 3, 4};
var uNum = num.Distinct().ToList();
var sums=(from num1 in uNum
        from num2 in uNum 
        where num1!=num2
        select num1+num2).Distinct();
foreach (var s in sums)
{
    Console.WriteLine(s);
}

- vzczc

Answer 6

无论你做什么，如果没有对输入值进行额外的限制，你都不能比O(n^2)更好，因为你必须遍历所有数字对。迭代将支配排序（你可以在O(n log n)或更快的时间内完成）。

- florin

---

是的，但对n^2个物品进行排序需要O(n^2 log n)的时间，因此排序永远不会占主导地位。 - user97370

Answer 7

这个问题已经困扰了我一天了。太棒了。

无论如何，很难摆脱它的n^2本质，但是由于您可以将要插入每个元素的范围限定在合并中，因此可以略微改善。

如果您查看您生成的所有列表，则具有以下形式:

(a[i], a[j]) | j>=i

如果将其旋转90度，则变为:

(a[i], a[j]) | i<=j

现在，合并过程应该取两个列表i和i+1（这对应于第一个成员始终为a[i]和a[i + 1]的列表），您可以通过 (a[i], a[j])的位置和(a[i + 1], a[j + 1])的位置来限定将元素(a[i + 1], a[j])插入到列表i的范围。

这意味着你应该按照 j 的相反顺序合并。我还不知道是否可以在跨越 j 方面利用它，但似乎有可能。

- Mat Noguchi

Answer 8

如果您正在寻找一种真正的语言无关解决方案，那么据我所知，您将感到非常失望，因为您只能使用for循环和一些条件语句。但是，如果您将其扩展到函数式语言或函数式语言特性（我在看你，LINQ），那么我的同事们可以用Ruby、Lisp、Erlang等优雅的示例填充此页面。

- John Downey