algorithm - Obtenez efficacement les sommes triées d'une liste triée

Translate

Vous avez une liste croissante de nombres, quel est l'algorithme le plus efficace auquel vous pouvez penser pour obtenir la liste ascendante des sommes de tous les deux nombres de cette liste. Les doublons dans la liste résultante ne sont pas pertinents, vous pouvez les supprimer ou les éviter si vous le souhaitez.

Pour être clair, je m'intéresse à l'algorithme. N'hésitez pas à publier le code dans la langue et le paradigme de votre choix.

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

Toutes les réponses

Translate

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] <= M [i, j + 1] et M [i, j] <= M [i + 1, j], il vous suffit d'examiner le coin supérieur gauche " coins »et choisissez le plus bas.

par exemple

  • seulement 1 coin supérieur gauche, choisissez 2
  • seulement 1, choisissez 5
  • 6 ou 8, choisissez 6
  • 7 ou 8, choisissez 7
  • 9 ou 8, choisissez 8
  • 9 ou 9, choisissez les deux :)
  • 10 ou 10 ou 10, choisissez tout
  • 12 ou 11, choisissez 11
  • 12 ou 12, choisissez les deux
  • 13 ou 13, choisissez les deux
  • 14 ou 14, choisissez les deux
  • 15 ou 16, choisissez 15
  • seulement 1, choisissez 16
  • seulement 1, choisissez 17
  • seulement 1, choisissez 18

Bien sûr, quand vous avezbeaucoupdes coins supérieurs gauche, alors cette solution découle.

Je suis à peu près sûr que ce problème est Ω (n²), car vous devez calculer les sommes pour chaque M [i, j] - à moins que quelqu'un n'ait un meilleur algorithme pour la sommation :)

La source
Translate

Plutôt que de coder cela, je suppose 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.

Lors de la première étape, nous commençons par 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 ont été générées 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, car 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 de fusion en fusionnant chaque liste ensemble plutôt que de fusionner le lot entier. À la fin, 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 ceci parce que n'importe qui peut rechercher le tri de fusion.

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

La source
Yale Lee
Translate

Vous pouvez le faire en deux lignes en python avec

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

Le coût en est n ^ 2 (peut-être un facteur de log supplémentaire pour l'ensemble?) Pour l'itération et s * log (s) pour le tri où s est la taille de l'ensemble.

La taille de l'ensemble pourrait être aussi grande que n * (n-1) / 2 par exemple si X = [1,2,4, ..., 2 ^ n]. Donc, si vous voulez générer cette liste, il faudra au moins n ^ 2/2 dans le pire des cas car c'est la taille de la sortie.

Cependant, si vous souhaitez sélectionner les k premiers éléments du résultat, vous pouvez le faire en O (kn) en utilisant un algorithme de sélection pour les matrices X + Y triées par Frederickson et Johnson (voir ici pour des détails sanglants). Bien que cela puisse probablement être modifié pour les générer en ligne en réutilisant le calcul et obtenir un générateur efficace pour cet ensemble.

@deuseldorf, Peter Il y a une certaine confusion à propos de (n!) Je doute sérieusement que deuseldorf signifiait "n factoriel" mais simplement "n, (très excité)!"

La source
Translate

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

Mon algorithme, dans 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, celle qui se prête mieux au codage par flux paresseux. 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, continuez avec 'foldl merge []', car c'est plus rapide.

La source
Translate

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 # 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);
}
La source
Translate

Quoi que vous fassiez, 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).

La source
Translate

Cette question me tourmente le cerveau depuis environ un jour maintenant. Impressionnant.

Quoi qu'il en soit, vous ne pouvez pas vous éloigner facilement de la nature n ^ 2 de celui-ci, 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 listesieti+1(qui correspondent à des listes où le premier membre est toujoursa[i]eta[i+1]), vous pouvez limiter la plage pour insérer l'élément(a[i + 1], a[j])dans la listeipar l'emplacement de(a[i], a[j])et l'emplacement de(a[i + 1], a[j + 1]).

Cela signifie que vous devez fusionner à l'envers en termes dej. Je ne sais pas (encore) si vous pouvez en tirer partijaussi bien, mais cela semble possible.

La source
Translate

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

La source