Effizient sortiert werden Summen von einer sortierten Liste

StackOverflow https://stackoverflow.com/questions/826

  •  08-06-2019
  •  | 
  •  

Frage

Sie haben eine aufsteigende Liste von zahlen, was ist der effizienteste Algorithmus können Sie denken, um die aufsteigende Liste von Summen von zwei zahlen in dieser Liste.Duplikate in der resultierenden Liste irrelevant sind, können Sie diese entfernen oder vermeiden Sie Sie, wenn Sie mögen.

Um klar zu sein, ich interessiere mich für den Algorithmus.Fühlen Sie sich frei, um post-code in einer beliebigen Sprache und Paradigmenwechsel, die Sie mögen.

War es hilfreich?

Lösung

Edit 2018:Sie sollten wahrscheinlich aufhören zu Lesen diese.(Ich kann aber nicht löschen es, wie es ist angenommen.)

Wenn Sie schreiben Sie die Summen wie diese:

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

Sie werden bemerken, dass, da M[i,j] <= M[i,j+1] und M[i,j] <= M[i+1,j], dann brauchen Sie nur zu prüfen, die oben Links "Ecken" und wählen Sie die niedrigste.

z.B.

  • nur 1 oberen linken Ecke, wählen Sie 2
  • nur 1, pick 5
  • 6 oder 8, pick 6
  • 7 oder 8, pick 7
  • 9 oder 8, wählen 8
  • 9 oder-9, wählen Sie beide :)
  • 10 oder 10 oder 10, pflücken,
  • 12 oder 11 pick 11
  • 12 oder 12, wählen Sie beide
  • 13 oder 13, wählen Sie beide
  • 14 oder 14, wählen Sie beide
  • 15 oder 16, pick 15
  • nur 1, pick 16
  • nur 1, pick 17
  • nur 1, pick 18

Natürlich, wenn Sie haben Menge von oben Links in die Ecken dann diese Lösung geht.

Ich bin mir ziemlich sicher, dieses problem ist Ω(n2), da Sie zur Berechnung der Summen für jedes M[i,j] - es sei denn, jemand hat einen besseren Algorithmus für die Summe :)

Andere Tipps

Anstatt die Programmierung dieses aus, ich denke, ich werde pseudo-code in Schritten und erklären, meine Logik, so dass eine bessere Programmierer kann poke Löcher in meine Logik, wenn nötig.

Im ersten Schritt beginnen wir mit einer Liste von zahlen der Länge n.Für jede Zahl, die wir brauchen, um erstellen Sie eine Liste der Länge n-1, weil wir nicht hinzufügen einer Zahl zu sich selbst.Am Ende haben wir eine Liste der über n sortierte Listen, die generiert wurde, in O(n^2) Zeit.

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

In Schritt 2, da die Listen einsortiert wurden-by-design (hinzufügen einer Nummer auf jedes element in einer sortierten Liste und die Liste wird noch sortiert werden), können wir einfach einen mergesort durch das Zusammenführen von einzelnen Listen zusammen, anstatt mergesorting die ganze Menge.Am Ende soll dies in O(n^2) Zeit.

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

Die merge-Methode wäre dann die normale merge-Schritt mit einem check, um sicherzustellen, dass es keine doppelten Summen.Ich werde Sie nicht schreiben, weil jeder kann die look-up-mergesort.

Das also ist meine Lösung.Der gesamte Algorithmus ist O(n^2) Zeit.Fühlen Sie sich frei, um jegliche Fehler oder Verbesserungen.

Sie können dies tun, in zwei Linien in python mit

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

Die Kosten dieses ist n^2 (vielleicht ein extra log Faktor für den Satz?) für die iteration und s * log(s) die für die Sortierung wobei s die Größe von dem set.

Die Größe der Satz könnte so groß sein wie n*(n-1)/2, für Beispiel, wenn X = [1,2,4,...,2^n].Also, wenn Sie möchten, erstellen Sie diese Liste, es wird nehmen mindestens n^2/2-im schlimmsten Fall-denn dies ist die Größe der Ausgabe.

Wenn Sie jedoch möchten, wählen Sie die ersten k Elemente der Ergebnis-Sie können dies in O(kn) anhand eines Auswahl-Algorithmus sortiert, X+Y-Matrizen durch Frederickson und Johnson (siehe hier für die blutigen details).Obwohl dies wahrscheinlich geändert werden, um zu generieren Sie online durch die Wiederverwendung von Berechnungen und erhalten eine effiziente generator für dieses set.

@deuseldorf, Peter Es gibt einige Verwirrung über die (n!) Ich bezweifle ernsthaft, deuseldorf gemeint "n Fakultät", sondern einfach "n, (sehr aufgeregt)!"

Das beste was ich tun konnte, ist die Erstellung einer matrix von Summen jedes paar und führen dann die Reihen zusammen, a-la-merge-sort.Ich fühle mich wie ich bin etwas fehlt einfach Einblicke, die zeigen wird, eine sehr viel effizientere Lösung.

Mein Algorithmus in 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)

Ich fand eine kleine Verbesserung, eine ist mehr geeignet zu faul stream-basierten Codierung.Anstelle der Zusammenführung der Spalten pair-wise, verschmelzen Sie alle auf einmal.Der Vorteil ist, dass Sie anfangen, Elemente der Liste sofort.

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

Jedoch, wenn Sie wissen, dass Sie ' re gehen zu verwenden, alle Summen, und es gibt keinen Vorteil, um zu bekommen, einige von Ihnen erwähnt, gehen mit 'foldl merge []', wie es schneller geht.

In 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);
}

Egal, was Sie tun, ohne zusätzliche Einschränkungen auf die Werte einzugeben, können Sie nicht besser als O(n^2), einfach, weil Sie haben, Durchlaufen Sie alle Paare von zahlen.Die iteration wird Dominieren Sortieren (was Sie tun können, in O(n log n) oder schneller).

Diese Frage wurde zu einer nervenaufreibenden mein Gehirn für etwa einen Tag zu kaufen.Genial.

Wie auch immer, Sie können nicht Weg von den n^2 Natur es ist so einfach, aber können Sie tun, etwas besser mit der merge-da kannst du gebunden, das Angebot zu legen jedem element.

Wenn Sie einen Blick auf all die Listen, die Sie erzeugen, Sie haben die folgende form:

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

Wenn Sie drehen es 90 Grad, Sie erhalten:

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

Nun, der merge-Prozess sollte sein, die zwei Listen i und i+1 (die entsprechen-Listen, in denen das erste Element ist immer a[i] und a[i+1]), können Sie gebunden Bereich einfügen, element (a[i + 1], a[j]) in Liste i durch die Lage des (a[i], a[j]) und die Lage des (a[i + 1], a[j + 1]).

Dies bedeutet, dass Sie sollten verschmelzen in reverse in Bezug auf j.Ich weiß nicht, (doch), wenn Sie können, nutzen Sie diese über j als gut, aber es scheint möglich.

Wenn Sie suchen für eine wirklich language-unabhängige Lösung, dann werden Sie bitter enttäuscht, meiner Meinung nach, denn Sie stecken mit einer for-Schleife und einige Bedingungen.Allerdings, wenn Sie es geöffnet haben, bis zu funktionalen Sprachen oder funktionale Sprache bietet (ich freu mich auf Euch LINQ) dann meine Kollegen hier können füllen diese Seite mit elegante Beispiele in Ruby, Lisp, Erlang, und andere.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top