Programm, um Personen einzuteilen

[blackbox]

Moin,
vielleicht kann jemand helfen:
es geht darum, Personen mit verschiedenen Spielstärken gleichmäßig in 5 Gruppen einzuteilen.

Der Ablauf ist folgender:
- Person X mit Stärke 5/10 kommt an. Ich gebe also in das Programm ein: 1 Person mit Stärke 5/10. Programm teilt diese Person X automatisch ein.
- nächste Person Y kommt, hat Stärke 10/10 > Programm soll diese einteilen
- das geht dann so weiter......

was nicht sein darf: Personen mit Stärke 10/10 kommen in die gleiche Gruppe. Denn dann wären die Gruppen zu unterschiedlich stark.
Jede Gruppe hat aber eine Soll-Grenze von 5 Personen. Erst wenn alle Gruppen voll sind, darf diese Soll-Grenze überschritten werden. Denn es ist nicht bekannt, wie viele Personen tatsächlich kommen. Es können insgesamt 20 Personen kommen, es können aber auch 30 Personen kommen. Wenn eine Person erstmal eingeteilt wurde, dann ist eine nachträgliche Änderung nicht mehr möglich.

Man könnte das Ganze auch manuell machen mit Listen usw. Aber eleganter und schneller wäre ein Programm.
Hat jemand eine Idee?

[Exxtreme]

Mhhh, da ist schon mal eine Sache unklar: werden die Spieler zunächst gesammelt und dann nach der Eingabe aller Spieler auf die Gruppen eingeteilt? Oder werden die Spieler direkt nach der Eingabe einer Gruppe zugewiesen? Wenn letzteres der Fall ist dann glaube ich nicht, dass man diese Aufgabe sehr zuverlässig lösen kann.

[blackbox]

Die Spieler kommen zufällig nacheinander und müssen daher sofort eingeteilt werden.

Es geht darum, dass die Gruppen möglichst gerecht eingeteilt werden, aber zu 100% wird das nicht funktionieren, das ist eingeplant.

[Asaraki]

Bisschen zu vage : Stell doch mal die Regeln klar auf, dann sollte es ziemlich straight forward sein

- möglichst ähnlicher Durchschnittswert über alle Gruppen
- keine Klumpung (zwei 10er erst in der gleichen Gruppe, wenn alle Gruppen einen 10er haben z.b oder darf der dann nie mitspielen? ;-))
- darf umgeteilt werden?
Etc

[Shink]

Überlege dir eine Formel, die einen Score berechnet, der alles mit einbezieht, was du für wichtig findest und rechne den für jede Gruppe+neue Person aus, wenn jemand Neuer kommt. Die Variante mit dem höchsten Score gewinnt. An der Berechnung des Scores kannst du dann rumfeilen nach ein paar Tests.

Ja, perfekt wird das nicht aber meiner Vermutung nach weißt du noch gar nicht, was die perfekten "Regeln" wären.

[blackbox]

Die Gruppen sollen idealweiser von der Anzahl der Spieler als auch von der Stärke ausgeglichen sein.

Also: 5 Spieler pro Gruppe mit einer Durchschnittsstärke von 5/10

Das Programm muss also nach und nach die Gruppen auffüllen.

Eine nachträgliche Veränderung ist nicht mehr möglich. Wenn z.B. ein Spieler mit Stärke 6/10 in Gruppe B eingeteilt wurde, dann ist eine Änderung nicht mehr möglich.

[Trap]

Das ist das online Matchmaking Problem, das man bei allen Team-basierten Onlinespielen hat.

https://dl.acm.org/doi/10.1145/3447548.3467074

[Gast]

Verstehe ich richtig: die Matches beginnen erst, wenn alle Spieler zugeteilt sind? Es gibt eine fixe Menge an Gruppen, und eine fixe Menge an Spielern? Das ist ja doch ein recht anderes Problem als bei Online Matches.
An sich bleibt dir mMn nicht viel übrig, als in dem Moment wo du zuteilst die Spielstärken aller Gruppen aufzuaddieren, und der Gruppe mit der geringsten Spielstärke den Spieler hinzuzufügen.
Die Regel, dass der Spieler just in dem Moment zugeordnet wird und bis Spielbeginn auch in der Gruppe bleibt, ist aber natürlich eine riesige Einschränkung. Ohne diese könnte man viel besser packen, könnte z.B. versuchen Spieler mit ähnlicher Stärke zusammenzupacken etc.
Inwieweit weißt du, welche Spieler wahrscheinlich sich anmelden werden?

[DocEW]

Hast du Informationen über die Verteilung der Spielstärken? Anders gefragt: sind alle Stärken gleich wahrscheinlich?

Ich gehe mal davon aus. Folgende spontane Idee: wenn die Stärke von 0 bis 10 geht, wäre ja die erwartete Durchschnittsstärke in jeder Gruppe 5. Dann könnte man das als "Zielwert" nutzen. Wenn du den nächsten Spieler einteilst packst du ihn in diejenige Gruppe, bei der er die Abweichung vom Zielwert am meisten verbessert (bzw. am wenigsten verschlechter).

Beispiel: in Gruppe 1 sind schon 3 Spieler [4, 5, 9], Durchschnitt also 6, und in Gruppe 2 sind 2 Spieler [7, 9], Durchschnitt also 8. Wenn du jetzt eine 5 ziehst wäre der neue Durchschnitt bei Einfügen in Gruppe 1 5,75 (=> Abweichung vom Zielwert verbessert sich von 1 auf 0,75, also um 0,25) und bei Einfügen in Gruppe 2 wäre es 7 (=> Verbesserung von 3 auf 2, also um 1). Da die Verbesserung bei Gruppe 2 höher ist, würde dort eingefügt.
Das ist sicher nicht perfekt, weil es z.B. nicht gut "erkennt", dass fast volle Gruppen jetzt als letzte Chance unbedingt eine kleine/große Zahl brauchen, aber es ist ein Anfang.

[Edit]: Achso, und dann kannst du noch ein paar Regeln frei nach gesundem Menschenverstand einfügen. Wenn z.B. mehrere Gruppen gleich gut für das nächste Einfügen geeignet sind, würde ich unterscheiden: wenn es durch das Einfügen sehr gut "passt", würde ich eher eine Gruppe voll machen, wenn es nicht gut passt, würde ich eher eine Gruppe wählen, wo noch viel Platz ist.

[Edit2]: Wenn ich dich richtig verstanden habe, ist es ein Multiway number partitioning (https://en.wikipedia.org/wiki/Multiway_number_partitioning) (mit k=5). Es ist ein NP-hartes Problem ("schwer" ;-)) und die Wiki-Seite gibt schon sehr viele Approximationsverfahren. Es gibt sogar noch eine gesonderte Wiki-Seite für Greedy number partitioning (https://en.wikipedia.org/wiki/Greedy_number_partitioning), was genau dein Anwendungsfall sein sollte (Spieler kommen nacheinander).

[Edit3]: Ansonsten lies einfach mal diese Doktorarbeit (https://escholarship.org/content/qt30g6n09q/qt30g6n09q_noSplash_ef9faa8716151ddad94c088224843a04.pdf?t=nmfl8z). :)

[blackbox]

Nein, weder Spieleranzahl noch Spielerstärke sind zu Anfang bekannt.
Man weiß nur die ungefähre Spieleranzahl. Grundsätzlich sind Spieler in den unteren Stärken naturgemäß häufiger vorhanden.

Wenn ein Spieler zugeordnet wurde, bleibt er auch dort. Eine nachträgliche Neuzuordnung ist organisatorisch nicht möglich. Die Spiele beginnen, sobald alle Spieler zugeordnet wurden. Aber: Nachzügler gibt es, denn nicht alle sind pünktlich.