Sortier-Algorithmus gesucht. 84Werte in 6 Listen verteilen

[Kostas]

Hallo zusammen,

ich habe genau 84 Werte zwischen 180.0 und 185.0 z.B.:182.8, 183.4, 183.9, 183.2 u.s.w.
Die Werte sollen aufgeteilt werden in sechs Listen je 14 Werte 14x6=84 Werte.
Dabei soll die Summe jeder einzelnen Liste nachezu den gleichen Summen-Wert ergeben.

Hat jemand eine Idee wie man das machen könnte.

Gruß Kostas

[Torpedo]

Das ist wahrscheinlich kein Sortierproblem, sondern ein Optimierungsproblem.
Man könnte zuerst die Summe aller Elemente bilden und diese durch 6 teilen. Dann weiß man, welche Summe jede Liste haben soll.
Den Rest könnte man mit Backtracking lösen.

[Kostas]

Zitat:

Zitat von Torpedo

Das ist wahrscheinlich kein Sortierproblem, sondern ein Optimierungsproblem.
Man könnte zuerst die Summe aller Elemente bilden und diese durch 6 teilen. Dann weiß man, welche Summe jede Liste haben soll.
Den Rest könnte man mit Backtracking lösen.

Danke für den Hinweis. Ich werde mir das Prinzip Backtracking mal anschauen das könnte interessant sein.
Dankeschön.

Gruß Kostas

[sx2008]

Man könnte es auch so lösen:
Die Zahlen werden anfangs der Reihe nach auf die 6 Listen verteilt.
Genauso wie man Karten an Pokerspieler ausgeben würde.

Dann wird die Summe jeder Liste gebildet und die Liste mit der grössten und der kleinsten Summe herausgegriffen.
Man berechnet den Durchschnitt (Summe / 14.0) und sucht nun in der Liste mit der grössten Summe eine Zahl, die grösser als dieser Durchschnitt ist.
In der Liste mit der kleinsten Summe sucht man eine Zahl, die kleiner als der Durchschnitt dieser Liste ist.
Die beiden gefundenen Zahlen werden einfach vertauscht.
Wenn man dieses Spielchen so ungefähr 50 bis 500 Mal wiederholt, sollten sich die Summen auf magische Weise angenähert haben.

[Medium]

Ein recht naiver Ansatz, der jedoch nicht immer zur optimalen Lösung führt, wäre einfach so zu beginnen wie sx2008 schrieb: Erst in jede Liste ein Wert. Die Liste, die die kleinste Summe hat, bekommt den nächsten Wert, und das so lange bis alles verteilt ist.

Ein möglicher Schritt um das zu optimieren wäre noch, die Ausgangsliste vor ab absteigend zu sortieren. So dass zuerst alle größten Werte verteilt werden, und zum Ende die kleineren kommen, welche dann keine brachialen Unterschiede ("Summensprünge") verusachen.
Das macht es zwar besser, aber die wirklich optimale Lösung wird man nur via Backtracking erhalten können wenn ich das richtig sehe. Das Problem scheint mir NP-vollständig zu sein.

[alzaimar]

Wenn man das auf eine Liste reduziert, sieht das fatal nach dem Knapsack-Problem aus.

[nahpets]

Hallo,

eventuell hilft ja auch das:

Zuerst alle Werte in eine temporäre Liste und diese sortieren.
Nun in die erste Liste den größten und den kleinsten Wert und diese aus der temporären Liste entfernen.
In die zweite Liste wiederum den größten und den kleinsten Wert und diese aus der temporären Liste entfernen.
In die dritte Liste wiederum den ...
In die vierte Liste wiederum ...
In die fünfte Liste ...
In die sechste ...
und wieder von vorne ... bis die temporäre Liste leer ist.
Je nach Verteilung der 84 Ursprungswerten könnte dies zumindest relativ nah an das gewünschte Ergebnis kommen.

Eventuell nach der Verteilung noch die Summe je Liste bilden und dann Einzelwerte zwischen den Listen tauschen, um die Summen anzunähern. Wenn ich das richtig sehe, liegt die durchschnittliche Differenz zwischen den Werten ja nur bei ca. 0,06. [OPTIMISMUS ON]Da dürfte diese Methode doch relativ nah beieinanderliegende Ergebnisse liefern.[OPTIMISMUS OFF]

Das erinnert mich ein bisserl an die Methode "PI erschießen", hierzu gibt es unter http://www.unixboard.de/vb3/showthread.php?t=12105 eine Methode in Java (am Ende der Seite - siehe auch Monte-Carlo-Algorithmus).