有效地获取排序列表的排序和

Question

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

需要明确的是，我对算法感兴趣。请随意以您喜欢的任何语言和范例发布代码。

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]，那么你只需要检查左上角“角”并选择最低的一个。

例如

• 左上角只有1个，选2个
• 只有1个，选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
• 只有1个，选16个
• 只有1个，选17个
• 只有1个，选18个

当然，当你有 地段 左上角然后这个解决方案就转移了。

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

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 

在步骤 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

合并方法将是正常的合并步骤，并进行检查以确保不存在重复的总和。我不会把这个写出来，因为任何人都可以查找归并排序。

这就是我的解决方案。整个算法的时间为O(n^2)。欢迎指出任何错误或改进之处。

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 cotorial”，但简单地说是“ n，（非常兴奋）！”

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

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

Answer 6

无论你做什么，如果没有对输入值的额外约束，你都无法做得比 O(n^2) 更好，因为你必须迭代所有数字对。迭代将主导排序（您可以在 O(n log n) 或更快的时间内完成排序）。

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 + 1], a[j]) 进入列表 i 通过位置 (a[i], a[j]) 和位置 (a[i + 1], a[j + 1]).

这意味着您应该按照以下方式反向合并 j. 。我（还）不知道你是否可以利用它 j 也是如此，但似乎有可能。

Answer 8

如果您正在寻找真正与语言无关的解决方案，那么我认为您会非常失望，因为您将陷入 for 循环和一些条件。然而，如果您将其开放给函数式语言或函数式语言特性（我指的是 LINQ），那么我的同事可以用 Ruby、Lisp、Erlang 等语言的优雅示例来填充此页面。