我们有一个递增的数字列表，我们可以想到哪种最有效的算法来获得该列表中每两个数字之和的递增列表。结果列表中的重复项无关紧要，我们可以删除它们，也可以根据需要避免重复。

明确地说，我对算法感兴趣。随意以我们喜欢的任何语言和范例发布代码。

解决方案：

如果我们正在寻找真正的语言不可知的## 解决方案，那么在我看来，我们将非常失望，因为我们将陷入for循环和一些条件句中。但是，如果我们将其开放给功能语言或者功能语言功能(我正在用LINQ看)，那么我的同事可以在此页面中使用Ruby，Lisp，Erlang等语言的精美示例来填充此页面。

我能想到的最好的办法是产生每对和的矩阵，然后将所有行合并在一起，即" a-la"合并排序。我感觉好像缺少一些简单的见解，这些见解将揭示一种更有效的## 解决方案。

我在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 []''，因为它更快。

我认为，与其逐步进行编码，不如说我将逐步对其进行伪编码并解释我的逻辑，以便更好的程序员在必要时可以在我的逻辑上作弊。

第一步，我们从长度为n的数字列表开始。对于每个数字，我们都需要创建一个长度为n-1的列表，因为我们没有在其自身上添加数字。到最后，我们有了一个在O(n ^ 2)时间内生成的大约n个排序列表的列表。

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

在第2步中，由于列表是按设计排序的(向排序列表中的每个元素添加一个数字，列表仍将排序)，我们可以简单地通过将每个列表合并在一起进行合并排序，而不是对整个批次进行合并排序。最后，这应该花费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

然后，合并方法将是常规合并步骤，并进行检查以确保没有重复的总和。我不会写出来，因为任何人都可以查找mergesort。

所以有我的## 解决方案。整个算法为O(n ^ 2)时间。随时指出任何错误或者改进。

在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

CLINQ：

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);
}

我们可以使用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)中执行此操作(有关详细信息，请参见此处)。尽管可以通过重新使用计算将其修改为在线生成它们，并为该集合获得有效的生成器。

@杜塞尔多夫，彼得
关于(n！)，我有些怀疑，杜塞尔多夫的意思是" n阶乘"，而仅仅是" n，(非常兴奋)！"，对此有些困惑。

这个问题困扰了我大约一天。惊人的。

无论如何，我们不能轻易摆脱它的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])。

这意味着我们应该按照j反向合并。我还不知道我们是否也可以在j之间使用它，但这似乎是可能的。

从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]，所以我们只需要检查左上方的"角落"，然后选择最低的一个。

例如

仅左上角1个，仅选择2个，选择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，仅选择1，仅选择17，选择18

当然，当左上角有很多东西时，此## 解决方案就会展开。

我很确定这个问题是(n2)，因为我们必须计算每个M [i，j]的和-除非有人对求和有更好的算法：)

无论我们做什么，都没有对输入值的添加约束，我们做不到O(n ^ 2)，这仅仅是因为我们必须遍历所有数字对。迭代将主导排序(我们可以在O(n log n)或者更快的速度中进行排序)。