Best Practice Die niedrigste Differenz zwischen zwei Listen ermitteln.

[DefconDev]

Ich habe eine Menge(Arraylist) aus maximal 8 und mindestens 2 Elementen(Zahlen). Die Elemente(Zahlen) der Menge sollen in einem weiteren Schritt in zwei neue Mengen aufgeteilt werden. Die zwei Mengen sollen anhand ihrer niedrigsten Differenz zueinander aufgeteilt werden.
Die zwei Mengen dürfen jeweils maximal 4 Elemente aufnehmen und jeweils mindestens 1 Element.

Bisher habe ich alle möglichen Mengen also (Array)Listen erstellt und miteinander verglichen um dann die beiden Mengen zu finden welche die niedrigste Differenz aufweisen.

Gibt es einen eleganteren Weg?

 

[mrBrown]

Wie ist denn niedrigste Differenz definiert?

 

[DefconDev]

Die Elemente der beiden Mengen werden summiert und dann wird die Differenz der beiden Summen gebildet. Wenn die Differenz null ist, dann ist die Differenz die niedrigste.

Oder wie darf ich dich verstehen?

 

[mrBrown]

Tendenziell dürfte etwas in die Richtung 'erst sortieren, dann auf zwei Listen verteilen' klappen

 

[DefconDev]

Das funktioniert aber nur wenn die Mengen immer gleich groß sind. Oder täusche ich mich? Also gleich groß im Sinne beide Mengen haben die selbe Anzahl an Elementen.

 

[mrBrown]

Nö, die Menge an Elementen sollte da keine Rolle spielen.

Kann man sicher sehr schön Testgetrieben umsetzen 😛

 

[DefconDev]

Wonach sortiere ich die denn? Meinst du die Mengen als solches oder die einzelnen Elemente?
Beispiel:

Menge = {19,105,55,40,41,75,100}

Verteile ich die Zahlen jetzt auf zwei neue Mengen, müsste ich vorher die die Menge absteigend sortieren nach ihrer Größe!?
Also :
Menge = {105,100,75,55,41,40,19}
Dann würde ich 105 mit den restlichen Zahlen vergleichen und die Zahl die als Nächtes zur ihr steht auf in die andere Menge aufteilen. Nächster Schritt wäre dann die nächsten Zahlen mit der 75 zu vergleichen und wieder die mit der niedrigsten Differenz zueinander aufzuteilen , nur diesmal kommt die kleinere von beiden zur Menge aus dem vorherigen Schritt zur höchsten Zahl. Am Schluss bleibt dann bei einer krummen Menge eine Zahl über, die wird dann der Menge zugespielt die bisher die niedrigste Summe im Vergleich zur anderen Summe steht.

neueMenge_1 ={105,55,41} Summe= 201
neueMenge_2 ={100,75,40} Summe= 215
neueMenge_1 ={100,55,41}+{19} neue Summe = 220

beide Mengen im Vergleich 220 - 215 = 5

Aber ist das allgemeingültig? Bzw. wird nach diesem Schema immer die niedrigste Differenz ausgelotet?

EDIT: Habe es gerade mal durchgerechnet, ist nicht allgemeingültig.

 

[mrBrown]

Die Menge absteigend sortieren, und die Werte der Reihe nach der jeweils kleinsten Menge zuteilen, meinte ich.

EDIT: Habe es gerade mal durchgerechnet, ist nicht allgemeingültig.

Für welche Beispiele den nicht?

 

[DefconDev]

Also habe es mit meiner oben genannte Menge gemacht:

Menge = {105,100,75,55,41,40,19}

Wenn ich dich richtig verstanden habe, ist dein Ansatz der wie ich es geschrieben habe oder?

Demzufolge:

neueMenge_1 ={105,55,41} Summe= 201+19 = 220
neueMenge_2 ={100,75,40} Summe= 215

Die Differenz ist dann 5. Aber folgende Konstellation macht mehr Sinn:

neueMenge_1={100,75,41} Summe = 216
neueMenge_2={105,55,40} Summe = 200+19 = 219 Die Differenz ist dann noch kleiner, denn 3.

 

[DefconDev]

Niemand eine Idee?

 

[DefconDev]

Nach ein wenig Recherche, fand ich nun heraus dass es keine Lösung gibt ohne alle möglichen Kombinationen zu vergleichen.

https://de.wikipedia.org/wiki/Partitionsproblem

Das Partitionsproblem gehört zu den 21 klassischen NP-vollständigen Problemen[2], von denen Richard M. Karp 1972 die Zugehörigkeit zur Klasse der NP-vollständigen Probleme zeigen konnte.