首页 / 知识

关于算法：有效获取排序列表的排序总和

2023-04-11 14:10:00

Efficiently get sorted sums of a sorted list

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

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

截至2018年编辑：您可能应该停止阅读此内容。 (但是我无法删除它，因为它已被接受。)

如果您这样写出总和：

1
2
3
4
5
6
7
8

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个

当然，当您的左上角有很多东西时，此解决方案就会发生变化。

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

我想我不会逐步进行编码，而是逐步地对其进行伪编码并解释我的逻辑，以便更好的程序员在必要时可以在我的逻辑上戳破洞。

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

1
2
3
4
5
6

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)时间。

1
2
3
4
5

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)时间。随时指出任何错误或改进。

您可以使用

在python的两行中执行此操作

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

此操作的成本是n^2(可能是集合的额外对数因子？)，迭代的成本是s * log(s)，其中s是集合的大小。

集合的大小可能与n*(n-1)/2一样大，例如，如果X = [1,2,4,...,2^n]。因此，如果要生成此列表，则在最坏的情况下它至少要花费n^2/2，因为这是输出的大小。

但是，如果您想选择结果的前k个元素，则可以使用Frederickson和Johnson的排序算法X+Y的选择算法，在O(kn)中执行此操作(有关详细信息，请参见此处)。尽管可以通过重新使用计算将其修改为在线生成它们，并为该集合获得有效的生成器。

@deuseldorf，彼得
关于(n!)有点困惑，我严重怀疑杜塞尔多夫的意思是" n阶乘"，而仅仅是" n，(非常兴奋)！"

无论您做什么，都没有对输入值的附加约束，您做不到比O(n ^ 2)好，这仅仅是因为您必须遍历所有数字对。迭代将主导排序(您可以在O(n log 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])的位置进入列表i。

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

在SQL中：

1
2
3
4
5
6
7
8
9

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：

1
2
3
4
5
6
7
8
9
10

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

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

我的算法，在Haskell中：

1
2
3
4
5
6
7
8
9
10
11

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)

我发现了一个较小的改进，该改进更适合基于延迟流的编码。而不是成对合并列，而是一次合并所有列。好处是您可以立即开始获取列表的元素。

1
2
3
4
5
6
7
8
9
10

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

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

排序列表算法升序