Si vous recherchez une solution vraiment indépendante du langage, vous serez très déçu à mon avis car vous serez coincé avec une boucle for et quelques conditions. Cependant, si vous l'avez ouvert à des langages fonctionnels ou à des fonctionnalités de langage fonctionnel (je vous regarde LINQ), mes collègues ici peuvent remplir cette page avec des exemples élégants en Ruby, Lisp, Erlang et autres.

Le mieux que je puisse trouver est de produire une matrice des sommes de chaque paire, puis de fusionner les lignes ensemble, un tri par fusion. J'ai l'impression qu'il me manque un aperçu simple qui révélera une solution beaucoup plus efficace.

Mon algorithme, en 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)

J'ai trouvé une amélioration mineure, qui se prête mieux au codage paresseux basé sur le flux. Au lieu de fusionner les colonnes par paires, fusionnez-les toutes en même temps. L'avantage étant que vous commencez à obtenir des éléments de la liste immédiatement.

-- 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

Cependant, si vous savez que vous allez utiliser toutes les sommes et qu'il n'y a aucun avantage à en obtenir certaines plus tôt, optez pour 'foldl merge []', car c'est plus rapide.

Plutôt que de coder cela, je pense que je vais le pseudo-coder par étapes et expliquer ma logique, afin que de meilleurs programmeurs puissent percer des trous dans ma logique si nécessaire.

Sur la première étape, nous commençons avec une liste de nombres de longueur n. Pour chaque nombre, nous devons créer une liste de longueur n-1 car nous n'ajoutons pas de nombre à lui-même. À la fin, nous avons une liste d'environ n listes triées qui a été générée en un temps 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 

À l'étape 2, parce que les listes ont été triées par conception (ajoutez un numéro à chaque élément dans une liste triée et la liste sera toujours triée), nous pouvons simplement faire un tri par fusion en fusionnant chaque liste plutôt que de trier par fusion tout le lot. Au final cela devrait prendre O(n^2) temps.

step 2 (sumlist) 
create an empty list mergedlist
for each list templist in sumlist
   set mergelist equal to: merge(mergedlist,templist)
return mergedlist

La méthode de fusion serait alors l'étape de fusion normale avec une vérification pour s'assurer qu'il n'y a pas de sommes en double. Je n'écrirai pas cela parce que n'importe qui peut rechercher mergesort.

Voilà donc ma solution. L'algorithme entier est en temps O(n^2). N'hésitez pas à signaler toute erreur ou amélioration.

En 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

Cette question me tourmente la tête depuis environ un jour maintenant. Génial.

De toute façon, vous ne pouvez pas vous éloigner facilement de la nature n^2, mais vous pouvez faire un peu mieux avec la fusion puisque vous pouvez délimiter la plage dans laquelle insérer chaque élément.

Si vous regardez toutes les listes que vous générez, elles ont la forme suivante :

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

Si vous le retournez à 90 degrés, vous obtenez :

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

Maintenant, le processus de fusion devrait prendre deux listes i et i+1 (qui correspondent à des listes où le premier membre est toujours a[i] et a[i+1]), vous pouvez délimiter la plage pour insérer l'élément (a[i + 1], a[j]) dans la liste i par l'emplacement de (a[i], a[j]) et le emplacement de (a[i + 1], a[j + 1]).

Cela signifie que vous devez fusionner à l'envers en termes de j. Je ne sais pas (encore) si vous pouvez également exploiter cela dans j, mais cela semble possible.

Modifier à partir de 2018 : vous devriez probablement arrêter de lire ceci. (Mais je ne peux pas le supprimer car il est accepté.)

Si vous écrivez les sommes comme ceci :

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

Vous remarquerez que puisque M[i,j]

Peu importe ce que vous faites, sans contraintes supplémentaires sur les valeurs d'entrée, vous ne pouvez pas faire mieux que O(n^2), simplement parce que vous devez parcourir toutes les paires de nombres. L'itération dominera le tri (ce que vous pouvez faire en O(n log n) ou plus rapidement).