algorithm - Erhalten Sie effizient sortierte Summen einer sortierten Liste

Translate

Sie haben eine aufsteigende Liste von Zahlen. Dies ist der effizienteste Algorithmus, den Sie sich vorstellen können, um die aufsteigende Liste von Summen von jeweils zwei Zahlen in dieser Liste zu erhalten. Duplikate in der resultierenden Liste sind irrelevant. Sie können sie entfernen oder vermeiden, wenn Sie möchten.

Um klar zu sein, ich interessiere mich für den Algorithmus. Sie können die Postleitzahl in einer beliebigen Sprache und einem beliebigen Paradigma veröffentlichen.

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

Alle Antworten

Translate

Bearbeiten ab 2018: Sie sollten wahrscheinlich aufhören, dies zu lesen. (Aber ich kann es nicht löschen, da es akzeptiert wird.)

Wenn Sie die Summen wie folgt ausschreiben:

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 feststellen, dass Sie, da M [i, j] <= M [i, j + 1] und M [i, j] <= M [i + 1, j], nur oben links untersuchen müssen " Ecken "und wählen Sie die niedrigste.

z.B

  • nur 1 obere linke Ecke, wählen Sie 2
  • nur 1, wählen Sie 5
  • 6 oder 8, wählen Sie 6
  • 7 oder 8, wählen Sie 7
  • 9 oder 8, wählen Sie 8
  • 9 oder 9, wähle beide aus :)
  • 10 oder 10 oder 10, alle auswählen
  • 12 oder 11, wählen Sie 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, wählen Sie 15
  • nur 1, wählen Sie 16
  • nur 1, wählen Sie 17
  • nur 1, wählen Sie 18

Natürlich, wenn Sie habenvielevon den oberen linken Ecken dann entwickelt sich diese Lösung.

Ich bin mir ziemlich sicher, dass dieses Problem Ω (n²) ist, da Sie die Summen für jedes M [i, j] berechnen müssen - es sei denn, jemand hat einen besseren Algorithmus für die Summierung :)

Quelle
Translate

Anstatt dies zu codieren, werde ich es in Schritten pseudocodieren und meine Logik erklären, damit bessere Programmierer bei Bedarf Löcher in meine Logik stechen können.

Im ersten Schritt beginnen wir mit einer Liste von Zahlen der Länge n. Für jede Zahl müssen wir eine Liste der Länge n-1 erstellen, da wir uns selbst keine Zahl hinzufügen. Am Ende haben wir eine Liste von ungefähr n sortierten Listen, die in O (n ^ 2) Zeit generiert wurden.

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 können wir einfach eine Zusammenführung durchführen, indem wir jede Liste zusammenführen, anstatt das gesamte Los zusammenzuführen, da die Listen nach Design sortiert wurden (fügen Sie jedem Element in einer sortierten Liste eine Nummer hinzu, und die Liste wird weiterhin sortiert). Am Ende sollte dies O (n ^ 2) Zeit dauern.

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

Die Zusammenführungsmethode wäre dann der normale Zusammenführungsschritt mit einer Überprüfung, um sicherzustellen, dass keine doppelten Summen vorhanden sind. Ich werde das nicht aufschreiben, weil jeder Mergesort nachschlagen kann.

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

Quelle
Yale Lee
Translate

Sie können dies in zwei Zeilen in Python mit tun

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

Die Kosten hierfür betragen n ^ 2 (möglicherweise ein zusätzlicher Protokollfaktor für die Menge?) Für die Iteration und s * log (s) für die Sortierung, wobei s die Größe der Menge ist.

Die Größe der Menge könnte beispielsweise so groß wie n * (n-1) / 2 sein, wenn X = [1,2,4, ..., 2 ^ n]. Wenn Sie also diese Liste erstellen möchten, dauert es im schlimmsten Fall mindestens n ^ 2/2, da dies die Größe der Ausgabe ist.

Wenn Sie jedoch die ersten k Elemente des Ergebnisses auswählen möchten, können Sie dies in O (kn) mithilfe eines Auswahlalgorithmus für sortierte X + Y-Matrizen von Frederickson und Johnson (siehe hier für blutige Details). Obwohl dies wahrscheinlich geändert werden kann, um sie online zu generieren, indem die Berechnung wiederverwendet wird und ein effizienter Generator für diesen Satz erhalten wird.

@deuseldorf, Peter Es gibt einige Verwirrung über (n!) Ich bezweifle ernsthaft, dass Deuseldorf "n Fakultät" bedeutet, aber einfach "n, (sehr aufgeregt)!"

Quelle
Translate

Das Beste, was ich mir einfallen lassen kann, ist, eine Matrix von Summen jedes Paares zu erstellen und dann die Zeilen zusammenzuführen, a-la-Merge-Sortierung. Ich habe das Gefühl, dass mir einige einfache Erkenntnisse fehlen, die eine viel effizientere Lösung aufzeigen.

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 habe eine kleine Verbesserung gefunden, die für Lazy Stream-basierte Codierung besser geeignet ist. Anstatt die Spalten paarweise zusammenzuführen, führen Sie alle gleichzeitig zusammen. Der Vorteil ist, dass Sie sofort Elemente der Liste erhalten.

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

Wenn Sie jedoch wissen, dass Sie alle Beträge verwenden werden und es keinen Vorteil hat, einige davon früher zu erhalten, gehen Sie zu 'foldl merge []', wie es schneller ist.

Quelle
Translate

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);
}
Quelle
Translate

Unabhängig davon, was Sie tun, können Sie ohne zusätzliche Einschränkungen der Eingabewerte nichts Besseres als O (n ^ 2) tun, einfach weil Sie alle Zahlenpaare durchlaufen müssen. Die Iteration dominiert die Sortierung (was Sie in O (n log n) oder schneller tun können).

Quelle
Translate

Diese Frage hat mein Gehirn seit ungefähr einem Tag erschüttert. Genial.

Wie auch immer, Sie können sich nicht leicht von der n ^ 2-Natur lösen, aber Sie können die Zusammenführung etwas besser machen, da Sie den Bereich zum Einfügen jedes Elements begrenzen können.

Wenn Sie sich alle von Ihnen erstellten Listen ansehen, haben sie die folgende Form:

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

Wenn Sie es um 90 Grad drehen, erhalten Sie:

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

Jetzt sollte der Zusammenführungsprozess zwei Listen umfasseniundi+1(die Listen entsprechen, in denen sich immer das erste Mitglied befindeta[i]unda[i+1]) können Sie den Bereich zum Einfügen eines Elements begrenzen(a[i + 1], a[j])in Listeidurch den Standort von(a[i], a[j])und der Standort von(a[i + 1], a[j + 1]).

Dies bedeutet, dass Sie in Bezug auf umgekehrt zusammenführen solltenj. Ich weiß (noch) nicht, ob Sie dies nutzen könnenjauch, aber es scheint möglich.

Quelle
Translate

Wenn Sie nach einer wirklich sprachunabhängigen Lösung suchen, werden Sie meiner Meinung nach sehr enttäuscht sein, da Sie mit einer for-Schleife und einigen Bedingungen nicht weiterkommen. Wenn Sie es jedoch für funktionale Sprachen oder funktionale Sprachfunktionen geöffnet haben (ich sehe Sie als LINQ an), können meine Kollegen hier diese Seite mit eleganten Beispielen in Ruby, Lisp, Erlang und anderen füllen.

Quelle