Algorithmus Ideen gesucht

• Spieler nach Bewertung sortieren
• Der Reihenfolge nach auf die verschiedenen Teams verteilen
• Bei jedem Durchgang die Richtung umkehren
• Profit

Ich fühle mich zurück in meine Schulzeit versetzt, wie ich stets als letzter bei der Teamverteilung auf der Bank gesessen habe und dann durch den Lehrer einem Team zugewiesen wurde... :(

Stefan P. schrieb:

• Der Reihenfolge nach auf die verschiedenen Teams verteilen
• Bei jedem Durchgang die Richtung umkehren

Meinst du das so?

1. Reihenfolge aufsteigend
2. Team 1: + Spieler 1., Team 2: + Spieler 2., Team 3: + Spieler 3. usw?
3. Ausgewählten Spieler von der Liste entfernt
4. Reihenfolge absteigend
5. Team 1: + Spieler 1. (von den Verbleibenden), Team 2: + Spieler 2., Team 3: + Spieler 3. usw?
6. Ausgewählten Spieler wieder von der Liste entfernt
7. Reihenfolge wieder aufsteigend
8. Team 1: + Spieler 1. (von den Verbleibenden), Team 2: + Spieler 2., Team 3: + Spieler 3. usw?

Das würde funktionieren allerdings bei gleichen Anwesenheiten immer die gleichen Teams erstellen. Wir möchten noch etwas Zufall dazu haben...

Da könnte ich beim Punkt 2. randomly so +/- 2...3 Spieler schwenken

Ich weiss schon, bei dem Punkt 2. die Teams-Reihenfolge randomisieren

Ich fühle mich zurück in meine Schulzeit versetzt, wie ich stets als letzter bei der Teamverteilung auf der Bank gesessen habe und dann durch den Lehrer einem Team zugewiesen wurde... :(

Schlechter Lehrer, solche Leute lässt man die Teams wählen, dann sind sie automatisch mit drin und keiner kann meckern.

X Fussballspieler haben Bewertungen z.B. von 1 bis 10. Sie sollen random aber ausgeglichen in Y Teams aufgeteilt werden.

Könnte man mit einem Monte-Carlo-Algorithmus lösen. Einfach alle Spieler zufällig verteilen, die Spielerwerte zu Teamwerten addieren und anschließend bewerten, ob das Ergebnis ausgeglichen genug ist. Wenn nicht, Vorgang wiederholen bis man ein Ergebnis erhält, was gut genug ist. Alternativ so viele Durchläufe wie in bestimmter Zeit möglich und die ausgeglichenste Verteilung ausgeben.

Edit: Man könnte auch probieren, passende Spieler zwischen dem höchst- und niedrigstbewertetem Team zu tauschen bis alle Teams den gleichen Score haben (oder ausreichend nahe beieinander liegen).

Dabei fällt mir auf, die Aufgabenstellung ist noch zu ungenau. Soll immer das optimalste bzw. ausgeglichenste Ergebnis gefunden werden, auch wenn dieses keinen Zufall mehr zulässt (weil es evtl. nur eines gibt) oder ist Zufall wichtiger und man braucht nur ein beliebiges Ergebnis oberhalb eines Grenzwertes?

Hi Ben,

good point, das würde ich mit einem "Schiebeparameter" den User bestimmen lassen, zwischen "optimal ausgeglichen" und "möglichst zufällig".

Danke für deine Inputs

Michal

Hier ist eine rekursive Routine sinnvoll.

Prinzip: ... 1.-füge nächsten Spieler hinzu 2.-Spieler als ausgewählt kennzeichnen 3.-Prüfe alle Bedingungen 4.Fertig, dann Return, sonst ... 5.-alle Bedingungen erfüllt, dann Prozedur erneut aufrufen 6.-sonst Spieler freigeben und 1. aufrufen

Werden Hausaufgaben heute nicht mehr selbstständig erledigt?

Michal P. schrieb:

Ich weiss schon, bei dem Punkt 2. die Teams-Reihenfolge randomisieren

Dann kannst du gleich von Anfang an zufällig zuweisen.

Stefan P. schrieb:

• Bei jedem Durchgang die Richtung umkehren

Ist tatsächlich besser. Würde man das nicht umkehren würde ein Team immer den jeweils besseren Spieler und ein Team den jeweils schlechteren Spieler bekommen. So bekommen die Teams "am Rand" abwechselnd einen besseren und schlechteren Spieler als der Durchschnittsspieler in dem jeweiligen Aufteilungsdurchlauf.

MaWin O. schrieb:

Werden Hausaufgaben heute nicht mehr selbstständig erledigt?

Seit guten 20 Jahren nicht mehr! Wir optimieren eine App für unseren kleinen Betriebssportverein

Dann kannst du gleich von Anfang an zufällig zuweisen.

Nicht ganz. Ich sammle mal alles in ein Stück:

1. Absteigend sortieren.
2. Von den besten je 1en Spieler zufällig je 1em Team zuweisen
3. Aufsteigend sortieren
4. Von den schlechtesten je 1en Spieler zufällig je 1em Team zuweisen
5. Zurück zu 1. bis alle Spieler verteilt sind.

Ein „Schiebeparameter“ im 2. und 4. regelt, in wie vielen Durchläufen (prozentuell) ein purer Zufall, und in wie vielen Durchläufen (prozentuell) „eine Ergänzung des schwächsten Teams“ als Zuweisungskriterium genommen wird.

So ist die App je nach Wunsch einstellbar.

Selbst ohne Zufall und wenn eine gerechte Lösung existiert, wird diese nicht unbedingt gefunden.

Beispiel: 5, 4, 3, 2, 1, 1 und Zuordnung nach dem Schema

A→max, B→max, A→min, B→min, ...

A→5, B→4, A→1, B→1, A→3, B→2.

Ergebnis ist also:

Team A = ( 5, 3, 1 ), Σ = 9 Team B = ( 4, 2, 1 ), Σ = 7

obwohl eine ausgewogene Lösung mit A = B = 8 existiert. Es lässt sich sogar erreichen, dass A die 3-fache Bewertung von B erhält, etwa mit 2, 1, 1, 0, 0, 0. Der Algorithmus liefert A = ( 2, 1, 0 ) und B = ( 1, 0, 0 ) obwohl eine gerechte Aufteilung A = ( 2, 0, 0 ) und B = ( 1, 1, 0 ) existiert.

Für den allgemainen Fall, dass die Team-Größen unterschiedlich sein dürfen, ist das Problem NP-vollständig und entspricht dem Rucksackproblem

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

Im Falle gleich großer Teams und unter der Voraussetzung, dass eine gerechte Aufteilung existiert, bin ich mir nicht ganz sicher.

Im allgemainen Fall mit 2n Spielern kann man 2^(2n) = 4^n verschiedene Teilmengen aus diesen bilden.

Im Fall |A| = |B| = n sind n-elementige Teilmengen aus einer Gesamtheit von 2n Elementen zu betrachten, und von diesen gibt es

$$\binom{2n}{n}=\frac{(2n)!}{n!^2}\approx \frac1{\sqrt{\pi n}}4^n$$

nach Stirling. Also ist die Anzahl möglicher Unterteilungen nicht wesentlich kleiner als im allgemeinen Fall.