Obtenez efficacement les sommes triées d'une liste triée
https://stackoverflow.com/questions/826
-
08-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Vous avez une liste ascendante de nombres. Quel est l'algorithme le plus efficace auquel vous puissiez penser pour obtenir la liste ascendante des sommes de 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 du code dans n'importe quelle langue et paradigme que vous aimez.
La solution
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], alors 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-en 2
- seulement 1, choisissez-en 5
- 6 ou 8, choisissez-en 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-en 15
- seulement 1, choisissez-en 16
- seulement 1, choisissez-en 17
- seulement 1, choisissez-en 18
Bien sûr, quand vous avez beaucoup des coins supérieurs gauches, cette solution incombe.
Je suis presque 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 :)
Autres conseils
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.
Dans 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, comme les listes ont été triées par conception (ajoutez un numéro à chaque élément d'une liste triée et la liste sera toujours triée), nous pouvons simplement effectuer un tri par fusion en fusionnant chaque liste ensemble plutôt que de trier par fusion l'ensemble.En fin de compte, cela devrait prendre un temps 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
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 car n'importe qui peut rechercher le tri par fusion.
Voilà donc ma solution.L'algorithme entier est en temps O(n^2).N'hésitez pas à signaler toute erreur ou amélioration.
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 est de n^2 (peut-être un facteur logarithmique 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 souhaitez générer cette liste, cela prendra au moins n^2/2 dans le pire des cas puisque 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 sur (n!) Je doute sérieusement que Deuseldorf signifiait "n factoriel" mais simplement "n, (très excité)!"
Le mieux que j'ai pu trouver est de produire une matrice de sommes de chaque paire, puis de fusionner les lignes ensemble, à la manière d'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 un flux.Au lieu de fusionner les colonnes par paires, fusionnez-les toutes en même temps.L’avantage étant que vous commencez immédiatement à obtenir des éléments de la liste.
-- 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.
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);
}
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).
Cette question me trotte dans la tête depuis environ un jour maintenant.Génial.
Quoi qu'il en soit, 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 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 aux listes où le premier membre est toujours a[i] et a[i+1]), vous pouvez délimiter la plage pour insérer un élément (a[i + 1], a[j]) dans la liste i par 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 de j.Je ne sais pas (encore) si vous pouvez en tirer parti j aussi, mais cela semble possible.
Si vous recherchez une solution véritablement indépendante du langage, vous serez à mon avis profondément déçu car vous serez coincé avec une boucle for et des conditions.Cependant, si vous l'avez ouvert aux langages fonctionnels ou aux 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.
