<p>You have an ascending list of numbers, what is the most efficient algorithm you can think of to get the ascending list of sums of every two numbers in that list.  Duplicates in the resulting list are irrelevant, you can remove them or avoid them if you like.</p>

<p>To be clear, I'm interested in the algorithm.  Feel free to post code in any language and paradigm that you like.</p>

[{'answer_id': 834, 'author': 'John Downey', 'author_id': 200, 'author_profile': 'https://Stackoverflow.com/users/200', 'pm_score': -1, 'selected': False, 'text': "<p>If you are looking for a truly language agnostic solution then you will be sorely disappointed in my opinion because you'll be stuck with a for loop and some conditionals. However if you opened it up to functional languages or functional language features (I'm looking at you LINQ) then my colleagues here can fill this page with elegant examples in Ruby, Lisp, Erlang, and others.</p>\n"}, {'answer_id': 840, 'author': 'Peter Burns', 'author_id': 101, 'author_profile': 'https://Stackoverflow.com/users/101', 'pm_score': 1, 'selected': False, 'text': "<p>The best I could come up with is to produce a matrix of sums of each pair, and then merge the rows together, a-la merge sort.  I feel like I'm missing some simple insight that will reveal a much more efficient solution.</p>\n\n<p>My algorithm, in Haskell:</p>\n\n<pre><code>matrixOfSums list = [[a+b | b &lt;- list, b &gt;= a] | a &lt;- list]\n\nsortedSums = foldl merge [] matrixOfSums\n\n--A normal merge, save that we remove duplicates\nmerge xs [] = xs\nmerge [] ys = ys\nmerge (x:xs) (y:ys) = case compare x y of\n    LT -&gt; x:(merge xs (y:ys))\n    EQ -&gt; x:(merge xs (dropWhile (==x) ys))\n    GT -&gt; y:(merge (x:xs) ys)\n</code></pre>\n\n<p>I found a minor improvement, one that's more amenable to lazy stream-based coding.  Instead of merging the columns pair-wise, merge all of them at once.  The advantage being that you start getting elements of the list immediately.</p>\n\n<pre><code>-- wide-merge does a standard merge (ala merge-sort) across an arbitrary number of lists\n-- wideNubMerge does this while eliminating duplicates\nwideNubMerge :: Ord a =&gt; [[a]] -&gt; [a]\nwideNubMerge ls = wideNubMerge1 $ filter (/= []) ls\nwideNubMerge1 [] = []\nwideNubMerge1 ls = mini:(wideNubMerge rest)\n    where mini = minimum $ map head ls\n          rest = map (dropWhile (== mini)) ls\n\nbetterSortedSums = wideNubMerge matrixOfSums\n</code></pre>\n\n<p>However, if you know you're going to use all of the sums, and there's no advantage to getting some of them earlier, go with '<code>foldl merge []</code>', as it's faster.</p>\n"}, {'answer_id': 884, 'author': 'Holtorf', 'author_id': 159, 'author_profile': 'https://Stackoverflow.com/users/159', 'pm_score': 2, 'selected': False, 'text': "<p>Rather than coding this out, I figure I'll pseudo-code it in steps and explain my logic, so that better programmers can poke holes in my logic if necessary. </p>\n\n<p>On the first step we start out with a list of numbers length n. For each number we need to create a list of length n-1 becuase we aren't adding a number to itself. By the end we have a list of about n sorted lists that was generated in O(n^2) time.</p>\n\n<pre><code>step 1 (startinglist) \nfor each number num1 in startinglist\n   for each number num2 in startinglist\n      add num1 plus num2 into templist\n   add templist to sumlist\nreturn sumlist \n</code></pre>\n\n<p>In step 2 because the lists were sorted by design (add a number to each element in a sorted list and the list will still be sorted) we can simply do a mergesort by merging each list together rather than mergesorting the whole lot.  In the end this should take O(n^2) time.</p>\n\n<pre><code>step 2 (sumlist) \ncreate an empty list mergedlist\nfor each list templist in sumlist\n   set mergelist equal to: merge(mergedlist,templist)\nreturn mergedlist\n</code></pre>\n\n<p>The merge method would be then the normal merge step with a check to make sure that there are no duplicate sums.  I won't write this out because anyone can look up mergesort.</p>\n\n<p>So there's my solution.  The entire algorithm is O(n^2) time.  Feel free to point out any mistakes or improvements.</p>\n"}, {'answer_id': 6458, 'author': 'vzczc', 'author_id': 224, 'author_profile': 'https://Stackoverflow.com/users/224', 'pm_score': 1, 'selected': False, 'text': '<p>In SQL:</p>\n\n<pre><code>create table numbers(n int not null)\ninsert into numbers(n) values(1),(1), (2), (2), (3), (4)\n\n\nselect distinct num1.n+num2.n sum2n\nfrom numbers num1\ninner join numbers num2 \n    on num1.n&lt;&gt;num2.n\norder by sum2n\n</code></pre>\n\n<p>C# LINQ:</p>\n\n<pre><code>List&lt;int&gt; num = new List&lt;int&gt;{ 1, 1, 2, 2, 3, 4};\nvar uNum = num.Distinct().ToList();\nvar sums=(from num1 in uNum\n        from num2 in uNum \n        where num1!=num2\n        select num1+num2).Distinct();\nforeach (var s in sums)\n{\n    Console.WriteLine(s);\n}\n</code></pre>\n'}, {'answer_id': 7842, 'author': 'Community', 'author_id': -1, 'author_profile': 'https://Stackoverflow.com/users/-1', 'pm_score': 2, 'selected': False, 'text': '<p>You can do this in two lines in python with</p>\n<pre><code>allSums = set(a+b for a in X for b in X)\nallSums = sorted(allSums)\n</code></pre>\n<p>The cost of this is <code>n^2</code> (maybe an extra log factor for the set?) for the iteration and s * log(s) for the sorting where s is the size of the set.</p>\n<p>The size of the set could be as big as <code>n*(n-1)/2</code> for example if <code>X = [1,2,4,...,2^n]</code>. So if you want to generate this list it will take at least <code>n^2/2</code> in the worst case since this is the size of the output.</p>\n<p>However if you want to select the first k elements of the result you can do this in O(kn) using a selection algorithm for sorted <code>X+Y</code> matrices by Frederickson and Johnson (<a href="http://arxiv.org/abs/0804.0936" rel="nofollow noreferrer">see here for gory details)</a>. Although this can probably be modified to generate them online by reusing computation and get an efficient generator for this set.</p>\n<p>@deuseldorf, Peter\nThere is some confusion about <code>(n!)</code> I seriously doubt deuseldorf meant &quot;n factorial&quot; but simply &quot;n, (very excited)!&quot;</p>\n'}, {'answer_id': 20701, 'author': 'Mat Noguchi', 'author_id': 1799, 'author_profile': 'https://Stackoverflow.com/users/1799', 'pm_score': 1, 'selected': False, 'text': "<p>This question has been wracking my brain for about a day now. Awesome.</p>\n\n<p>Anyways, you can't get away from the n^2 nature of it easily, but you can do slightly better with the merge since you can bound the range to insert each element in.</p>\n\n<p>If you look at all the lists you generate, they have the following form:</p>\n\n<p><code>(a[i], a[j]) | j&gt;=i</code></p>\n\n<p>If you flip it 90 degrees, you get:</p>\n\n<p><code>(a[i], a[j]) | i&lt;=j</code></p>\n\n<p>Now, the merge process should be taking two lists <code>i</code> and <code>i+1</code> (which correspond to lists where the first member is always <code>a[i]</code> and <code>a[i+1]</code>), you can bound the range to insert element <code>(a[i + 1], a[j])</code> into list <code>i</code> by the location of <code>(a[i], a[j])</code> and the location of <code>(a[i + 1], a[j + 1])</code>.</p>\n\n<p>This means that you should merge in reverse in terms of <code>j</code>. I don't know (yet) if you can leverage this across <code>j</code> as well, but it seems possible.</p>\n"}, {'answer_id': 97294, 'author': 'porges', 'author_id': 10311, 'author_profile': 'https://Stackoverflow.com/users/10311', 'pm_score': 5, 'selected': True, 'text': '<p>Edit as of 2018: You should probably stop reading this. (But I can\'t delete it as it is accepted.)</p>\n\n<p>If you write out the sums like this:</p>\n\n<pre><code>1 4  5  6  8  9\n---------------\n2 5  6  7  9 10\n  8  9 10 12 13\n    10 11 13 14\n       12 14 15\n          16 17\n             18\n</code></pre>\n\n<p>You\'ll notice that since M[i,j] &lt;= M[i,j+1] and M[i,j] &lt;= M[i+1,j], then you only need to examine the top left "corners" and choose the lowest one.</p>\n\n<p>e.g.</p>\n\n<ul>\n<li>only 1 top left corner, pick 2</li>\n<li>only 1, pick 5</li>\n<li>6 or 8, pick 6</li>\n<li>7 or 8, pick 7</li>\n<li>9 or 8, pick 8</li>\n<li>9 or 9, pick both :)</li>\n<li>10 or 10 or 10, pick all</li>\n<li>12 or 11, pick 11</li>\n<li>12 or 12, pick both</li>\n<li>13 or 13, pick both</li>\n<li>14 or 14, pick both</li>\n<li>15 or 16, pick 15</li>\n<li>only 1, pick 16</li>\n<li>only 1, pick 17</li>\n<li>only 1, pick 18</li>\n</ul>\n\n<p>Of course, when you have <em>lots</em> of top left corners then this solution devolves.</p>\n\n<p>I\'m pretty sure this problem is Ω(n²), because you have to calculate the sums for each M[i,j] -- unless someone has a better algorithm for the summation :)</p>\n'}, {'answer_id': 97567, 'author': 'florin', 'author_id': 18308, 'author_profile': 'https://Stackoverflow.com/users/18308', 'pm_score': 1, 'selected': False, 'text': '<p>No matter what you do, without additional constraints on the input values, you cannot do better than O(n^2), simply because you have to iterate through all pairs of numbers.  The iteration will dominate sorting (which you can do in O(n log n) or faster).</p>\n'}]
['https://Stackoverflow.com/questions/826', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/101/']