Ein Algorithmus, um ein Paar Summen aus einer Liste von Zahlen zu finden?

Question

Angenommen, Sie haben die folgende Liste von Zahlen, {3,6,10,9,13,16,19}, nicht unbedingt in dieser Reihenfolge. Nun, da ich nicht weiß, dass dies die Menge der möglichen Kombination der Menge {3,6,10} ist, gibt es einen Algorithmus in jeder Programmiersprache, der verwendet werden kann, um diese Kombination effizient zu finden. Grundsätzlich möchte ich die Liste von der Gesamtmenge wiederherstellen - wo alle Zahlen enthalten sind. Was ist ein effizienter Algorithmus? Ich möchte das Rad nicht neu erfinden, wenn eines bereits existiert?

Answer 1

Für den allgemeinen Fall, wo es eine beliebige Anzahl von Elementen sein kann, hier ist ein O (q * log (q)) Algorithmus, wobei q die Größe der Eingabeliste ist:

1. Sortieren Sie die Liste q in aufsteigender Reihenfolge.
2. Entfernen Sie das kleinste Element, m, und fügen Sie es zur Ergebnismenge hinzu. Entferne es von q.
3. Iterieren über q. Behalte eine Liste von Zahlen, die wir gesehen haben. Wenn wir eine Zahl sehen, die ist (eine Zahl, die wir schon + m gesehen haben), dann wirf sie weg. Dies sollte die Hälfte der Zahlen behalten (all jene, die nicht m betreffen).
4. Wiederholen Sie den Vorgang ab Schritt 2, bis alle Nummern gefunden wurden.

Hier ist eine Implementierung dieses Algorithmus in Python:

def solve(q): 
    q = sorted(q) 
    x = [] 
    while q: 
     x.append(q[0]) 

     s = [False]*len(q) 
     s[0] = True 
     j = 1 

     for i in range(1, len(q)): 
      if q[i] == q[0] + q[j]: 
       s[i] = True 
       j += 1 
       while j < len(q) and s[j]: 
        j += 1 

     q = [k for k, v in zip(q, s) if not v] 
    return x 

s = [1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99] 
from itertools import combinations 
q = list(sum(x) for r in range(1, len(s) + 1) for x in combinations(s, r)) 
print(solve(q)) 

Ergebnis:

[1, 3, 7, 12, 13, 20, 25, 31, 32, 33, 62, 78, 80, 92, 99] 

---

Ursprüngliche Antwort:

Unter der Annahme, dass es nur drei Zahlen in der sind Liste, und dass keine Nummer negativ sein kann:

Zwei der Zahlen müssen die kleinsten zwei Zahlen in der Liste sein. Die größte Zahl muss die Summe aller drei sein. Durch Subtraktion können Sie die dritte Zahl finden.

Answer 2

1) Finden Sie die kleinsten zwei Zahlen, diese müssen ein Teil der ursprünglichen Liste sein.

2) Finden Sie ihre Summe, alles kleinere in der Liste muss Teil der ursprünglichen Liste sein.

3) Suchen Sie die nächstkleinere Summe und wiederholen Sie die Operation, bis alle Summen zweier Zahlen erreicht sind.

Jedes Mal, wenn Sie der ursprünglichen Liste eine Zahl hinzufügen oder eine Summe suchen, entfernen Sie sie aus der großen Liste.

4) Fahren Sie mit 3 Zahlensummen fort und erhöhen Sie den Wert, bis die große Liste leer ist.

Edit:

die nächste kleinste Summe zu finden erfordert eine sortierte Liste Ihrer Zahlen. Wenn Ihre Liste A, B, C, D, E ist, dann ist die kleinste Summe A + B und die nächstkleinere Summe ist A + C.

Die Leistung ist so schrecklich wie es geht: 2^N, aber wenn ich Ihre Frage richtig lese, enthält die Liste Ihre ursprüngliche Liste und alle möglichen Summen, mit denen Sie die Leistung erheblich steigern könnten.

Zum Beispiel wissen Sie, wie viele Zahlen Sie suchen, was bedeutet, dass Sie wissen, wenn Sie nur eine mehr benötigen, und da Sie auch die größte Zahl in der Liste kennen, ist die letzte Zahl die größte Zahl minus alle Zahlen bereits zu Ihrer ursprünglichen Liste hinzugefügt.

Answer 3

So machen Sie es. Oder zumindest ist es eine naive Lösung.

Zuerst bestellen Sie die Nummern in aufsteigender Reihenfolge. Angenommen, A ist die Liste der geordneten Ergebnisse und S ist die Menge der minimalen Zahlen, aus denen Sie A.

Schleife durch A. Obwohl es keine Untermenge von S gibt, die zu einer _i addiert hinzufügen neue Nummer zu S, so dass es geht.

In der ersten Iteration wird min (A) hinzugefügt. Die zweite Zahl wird wahrscheinlich in S sein. Dies ist ziemlich rechenintensiv, weil Sie für jede Zahl, die Sie in A untersuchen, sicherstellen müssen, dass eine Teilmenge von S existiert, die zu ihr addiert und dass Sie keine Zahl hinzufügen Das erzeugt eine Teilmenge von S, die zu etwas in A addiert.

Sie können dies etwas optimieren, indem Sie jedes Mal, wenn Sie S eine Zahl hinzufügen, alle möglichen Summen einschließlich des neuen Elements berechnen und aus A entfernen. Keep Gehen Sie bis Sie leer A.

Es wird kompliziert, wenn die Zahlen negativ sein können, aber Sie werden dies sehen, weil es ein negatives Element von A sein muss, damit dies möglich ist.