Erkennen von Zahlenpaaren

[Namenloser]

Zitat von BUG:

Mhm, auf den ersten Blick sah es nach Partition aus, allerdings scheinst du ja eine passende Partition zu haben.

Ich hätte es eher als Rucksackproblem identifiziert, wobei es ja letztlich auf dasselbe herausläuft: Beide sind NP-vollständig.

Mein Lösungsansatz ist ausgehend von dieser Idee: Mal angenommen, es gäbe nur Kombinationen der Länge 2. Dann wäre es ja einfach: Man subtrahiert einfach alle Zahlen aus Menge1 von allen Zahlen aus Menge2. Dann muss man nur noch prüfen, welche dieser Differenzen auch tatsächlich in Menge1 liegen. Schon hat man alle gültigen Paare.

Wenn man mehr als zwei Elemente pro Kombination zulässt, muss man den Ansatz etwas verallgemeinern: Man muss nun für jede Differenz schauen, ob sie wiederum durch eine Kombination von Elementen aus Menge1 gebildet werden kann. Das kann man wieder mit dem gleichen Algorithmus machen. So macht man es iterativ immer weiter, bis man am Ende Summen hat, die man mit einem einzelnen Element erfüllen kann. Der Trick ist, sich für jede Zwischensumme immer die kürzeste, bereits gefundene Kombination zu merken (Prinzip der Dynamischen Programmierung). Da die Kombinationen immer nur länger werden können, ist die erste gefundene Kombination automatisch immer auch die kürzeste.

Ich habe das mal als Proof-of-Concept implementiert. TCombinationTable sollte man in einer richtigen Implementierung als Hashtable implementieren, dazu war ich jetzt aber zu faul.

Das Programm gibt allerdings immer nur die kürzeste Kombination aus, nicht, ob es noch weitere Kombinationen gibt. Das wäre IMO nur noch mit Brute-Force zu machen.

Beispiel Ein- und Ausgabe:

Delphi-Quellcode:

PARTS: array [0..8] of Integer = (2,6,7,1,6,15,7,4,1);
SUMS: array [0..3] of Integer = (16,13,9,11);

Code:

16 = 15 + 1
13 = 7 + 6
9 = 7 + 2
11 = 7 + 4

Delphi-Quellcode:

PARTS: array [0..16] of Integer = (2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1);
SUMS: array [0..6] of Integer = (1,2,3,16,13,9,11);

Code:

2 = 2
1 = 1
3 = 2 + 1
9 = 2 + 1 + 2 + 1 + 2 + 1
11 = 1 + 1 + 2 + 1 + 2 + 1 + 2 + 1
13 = 1 + 1 + 1 + 1 + 2 + 1 + 2 + 1 + 2 + 1
16 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 1 + 2 + 1 + 2 + 1

Scheint zu funktionieren.

Edit: Habe noch ein paar Fehler in meinem Code korrigiert, wegen denen die Laufzeit deutlich schlechter war als nötig.