algorithm -有效地获得排序列表的排序总和

Translate

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

要清楚,我对算法感兴趣。随意以您喜欢的任何语言和范例发布代码。

This question and all comments follow the "Attribution Required."

所有的回答

Translate

从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]的总和-除非有人有一个更好的求和算法:)

来源
Translate

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

第一步,我们从长度为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)时间。随时指出任何错误或改进。

来源
Yale Lee
Translate

您可以使用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,(非常兴奋)!”

来源
Translate

我能想到的最好的办法是产生每对和的矩阵,然后将所有行合并在一起,即“ 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 []”,因为它更快。

来源
Translate

在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);
}
来源
Translate

无论您做什么,都没有对输入值的附加限制,您做不到O(n ^ 2),这仅仅是因为您必须遍历所有数字对。迭代将主导排序(您可以用O(n log n)或更快速地进行排序)。

来源
Translate

这个问题困扰了我大约一天。太棒了

无论如何,您无法轻易摆脱它的n ^ 2性质,但是由于可以绑定范围以插入每个元素,因此合并可以做得更好。

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

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

如果将其翻转90度,则会得到:

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

现在,合并过程应该包含两个列表ii+1(对应于第一个成员始终为a[i]a[i+1]),您可以将范围绑定到插入元素(a[i + 1], a[j])进入清单i按位置(a[i], a[j])和位置(a[i + 1], a[j + 1]).

这意味着您应该在以下方面进行反向合并:j。我尚不知道您是否可以在j同样,但似乎有可能。

来源
Translate

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

来源