Mathematisches Problem und wie setzt man das um ?

[joschi50]

Ich habe ein grundlegendes Problem welches ich weder mathematisch noch programmtechnisch gelöst bekomme. Dafür sind meine Kenntnisse zu gering.

Beispiel:
Ich habe z.b. 28 Teams die aus je 2 Personen bestehen.

Diese Teams sollen jetzt in 6 Spielrunden gegeneinander spielen und zwar - kein Team spielt jemals gegen das gleiche Team.

Bei 8 Teams kann ich das noch von Hand durchrechnen, es gibt dann 5 mögliche Spielrunden.
Runde 1
T1   T8
T2   T7
T3   T6
T4   T5
Runde 2
T1   T5
T2   T6
T3   T7
T4   T8
Runde 3
T1   T4
T2   T3
T5   T7
T6   T8
Runde 4
T7   T1
T2   T8
T5   T3
T4   T6
Runde 5
T1   T2
T3   T4
T5   T6
T7   T8

Da die Rundenzahl auf 6 beschränkt ist, müssten also max. 6 Durchläufe erfolgen wobei die vorherigen Ergebnisse berücksichtigt werden müssten.

Das alles soll in einer Tabelle gespeichert werden wie folgt:

Code [Auswählen] Erweitern

ID runde team gegner
1 1 1 8
2 1 2 7
3 1 3 6
4 1 4 5
5 2 1 5
6 2 2 6
7 2 3 7
8 2 4 8
9 3 3 2
10 3 4 1
11 3 5 7
12 3 6 8
13 4 7 1
14 4 8 2
15 4 3 5
16 4 4 6
17 5 4 3
18 5 1 2
19 5 8 7
20 5 6 5
Blickt da jemand durch ?

[markusxy]

welches ich weder mathematisch noch programmtechnisch

Du wirst es erstmal logisch lösen müssen, oder?
Was ist dein konkretes Problem dabei?
Bei mir ging es nur darum alle möglichen Kombinationen zu finden - war aber ein ganz anderes Thema.

Mangels Lösung habe ich das Problem mit 2, dann 3 und dann mit dann mit 4 verschiedenen Möglichkeiten dargestellt.
Es sollte dann recht schnell eine Logik zu erkennen sein. Versuch es mal - wenn man nicht gleich aufgibt findet man auch die Lösung.
Die Spielrunden sind dann ein anderes Thema - das habe ich nicht gebraucht, aber das ist dann per Code ja recht einfach zu lösen. Eine Mannschaft darf eben bei einer Runde nur einmal vorkommen.

[markusxy]

Bist du jetzt weiter gekommen, oder wartest du auf das Christkind?

[ebs17]

Bei 8 Teams ... gibt dann 5 mögliche Spielrunden

Bei 8 Teams gibt es für ein Team jeweils 7 Gegner, also maximal 7 Spielrunden.

Ich habe z.b. 28 Teams ...
Diese Teams sollen jetzt in 6 Spielrunden gegeneinander spielen und zwar - kein Team spielt jemals gegen das gleiche Team.

Diese Anforderung ist in der beigefügten Anlage erfüllt (Prozedur Main ausführen).

Strategie:

Code [Auswählen] Erweitern

SELECT
   A.Team,
   B.Team AS Gegner,
   Int(Rnd(A.Team) * 1000000) AS X
FROM
   tblTeams AS A,
   tblTeams AS B
WHERE
   A.Team < B.TeamMit dieser Abfrage werden alle denkbaren Paarungen ermittelt, bei 28 Teams sind das 378. Dazu vergebe ich gleich noch eine Zufallszahl X (als ID). Diese Paarungen liegen nun quasi in einer Lostrommel.

Jetzt wird nur einzeln gezogen und verteilt. Jede Paarung wird selbstredend nur einmal gezogen, pro Spielrunde darf ein Team nur einmal vorkommen.

Die Aufteilung der Paarungen auf die maximale Anzahl an Spielrunden gelingt mit der vorgelegten Lösung nicht vollständig, bei 28 Teams in 27 Spielrunden gibt es eine Verteilung von 370 bis 372 Paarungen von den 378 vorhandenen.

[joschi50]

Hallo Ebs,

erst mal entschuldigung für die lange Antwortzeit. Wir waren in Urlaub :-)
Toll wie Du an die Sache herangegangen bist und vielen Dank für die Zeit die Du investiert hast.
Dieser Ansatz geht schon in die Richtung die ich brauche (wäre dazu leider selber nicht in der Lage).
Mir fällt jedoch auf, dass in Durchgängen doppelte Teams vorkommen.
Ich habe es mal mit 16 Teams probiert, hier ein Ausschnitt aus dem Ergebnis der Paarungen:

Code [Auswählen] Erweitern

ID Durchgang Team Gegner X
153 1 1 7 2505
154 1 1 14 4019
155 1 9 14 10293
156 1 6 15 28246
157 1 9 16 50045
158 1 8 10 74950
159 1 4 8 77980
160 1 9 11 78708
161 2 6 13 99409
162 2 8 14 108785
163 2 1 12 111432
164 2 8 9 114332
165 2 4 15 145000
166 2 10 14 151656
167 2 3 9 151756
168 2 4 13 152676
169 3 7 14 176886
170 3 4 6 178693
171 3 10 13 183076
172 3 12 14 188131
173 3 1 13 195534
174 3 1 16 203582
175 3 7 13 205047
176 3 11 16 206485
In Durchgang 1 spielt Team 1 gleich 2 x ebenso Team 14 etc
Das darf nicht sein. Jedes Team muss einmal gegen einen anderen Gegner antreten.
Ist der Fehler bei mir oder im Programm ?

Grüße
Jochen

[ebs17]

Ja, da ist noch ein Fehler (der vermutlich auch die unvollständige Verteilung der Paarungen erklären könnte). Bei einem Entspannungsbad sind mir nebenbei die Schuppen von den Augen gefallen.
Ich melde mich noch einmal.

[Köbi]

Hallo Eberhard

Bei einem Entspannungsbad sind mir nebenbei die Schuppen von den Augen gefallen.

Man nimmt doch heuzutage kein Entspannungsbad mehr. Man duscht, höchstens fünf Minuten, so wie es die hochwohllöbliche Regierung empfiehlt.  

Ach ja, und Schuppen fallen einem nicht von den Augen, sondern aus den Haaren (sofern solche noch vorhanden sind).

[ebs17]

@Köbi: In einem Oberlehrer- und Klugscheißerforum wären Deine Weisheiten sicher enorm gefragt. Hier kannst Du davon ausgehen, dass manche sich manches durchaus verdienen.
Es könnte aber auch sein, dass Du ein sprachliches Bild nicht verstehen kannst, wenn kein Smiley als Holzhammer drangehängt ist.

Wie sehen denn Deine fachlichen Gedanken zu Jochens Aufgabenstellung aus? Gibt es da etwas?

[joschi50]

Hallo Ebs,

ich muss dich übrigens in einem Punkt korrigieren:
Richtig ist, dass es bei 8 Teams jedes Team 7 mögliche Gegner hat.
Dennoch ergeben sich keine 7 Spielrunden da dann der Fall einträte, dass in einer Spielrunde zwei Teams gegeneinander spielen, welche schon einmal gegeneinander gespielt haben.
Genau das soll ja vermieden werden.
Am Anfang meiner Frage habe ich die 5 möglichen Konstellationen eingestellt.
Ich finde keine 2 weiteren Spielrundenpaarungen die der Anforderung entsprechen.

Danke nochmals für Deine Mühe.

[markusxy]

@Köbi: In einem Oberlehrer- und Klugscheißerforum wären Deine Weisheiten sicher enorm gefragt.

Ernsthaft Eberhard, selbst wie ein Trampeltier in sämtlichen Foren unterwegs, und dann nicht mal den geringsten Spaß verstehen.
Es ist doch immer das Gleiche. Diejenigen die überall austeilen, verstehen selbst nicht mal den geringsten Spaß, gehst wohl in den Keller zum Lachen.


Schöne Grüße von einem anderen Klugscheißer,
der so was perverses leider nicht unkommentiert stehen lassen kann.

Und ja, das Bilden der Spielrunden ist genau so wenig ein Problem, so wie auch das bilden der Teams keines ist.
Will dich aber nicht um deinen Lebensinhalt berauben, weil so ganz ohne Anstrengung von Seiten des Fragenden gibts bei mir keine Lösung.

[ebs17]

Dennoch ergeben sich keine 7 Spielrunden ...

Praxisbeispiel: In der deutschen Bundesliga spielen 18 Mannschaften. Eine Hinrunde wie auch die Rückrunde besteht aus 17 Spieltagen.

[joschi50]

Gegenbeispiel mit 8 Teams damit es nicht so viel Schreibarbeit ist:
1:2, 1:3, 1:4, 1:5; 1:6, 1:7, 1:8 (1. möglicher Durchlauf) jeder spielt gegen einen neuen Gegner
2:3, 2:4, 2:5, 2:6; 2:7, 2:8 (2. möglicher Durchlauf) 2:1 haben schon gegeneinander gespielt
3:4, 3:5, 3:6, 3:7, 3:8 (3. möglicher Durchlauf)1:3 , 3:2 haben schon gegeneinander gespielt
4:5, 4:6, 4:7, 4:8 (4. möglicher Durchlauf) 4:1, 4:2 und 4:3 haben schon gegeneinander gespielt
5:6, 5:7, 5:8  (5. möglicher Durchlauf) 5:1, 5:2, 5:3, 5:4 haben schon gegeneinander gespielt
6:7, 6:8 (6. möglicher Durchlauf) 6:1, 6:2, 6:3, 6:4, 6:5 haben schon gegeneinander gespielt
7:8 (7. möglicher Durchlauf) 7:1, 7:2, 7:3, 7:4, 7:5, 7:6 haben schon gegeneinander gespielt

Damit ergeben sich 28 Kombinationen die garantieren, dass nie das selbe Team gegeneinander spielt.
Aus diesen 28 Kombinationen müssen jetzt max. 6 Spielrunden erzeugt werden in denen alle 8 Teams antreten.
Und da komme ich auf genau 5 Runden. 8 Paarungen die übrig bleiben können nicht als Turnierrunde gespielt werden.
Streiche ich die Spielpaarungen aus meiner Rundenliste ganz oben, dann bleiben folgende Paarungen ungespielt übrig:
1:3, 1:6, 2:4, 2:5, 3:8, 4:7, 5:8 und 6:7

[Köbi]

@markus888
Vielen Dank. Du hast mir eine Antwort auf Eberhards Humorlosigkeit erspart.

Gruss, Köbi

[markusxy]

@joschi50,
bei 8 Teams wären es 7 Runden wenn alle Mannschaften einmal gegeneinander spielen. Im Prinzip streichst du davon 2 Runden damit du auf 5 Runden kommst. Die Frage ist natürlich warum nicht 7 Runden gespielt wird - aber im Prinzip ist es egal.

[Beaker s.a.]

Hallo,

Aus diesen 28 Kombinationen müssen jetzt max. 6 Spielrunden erzeugt werden in denen alle 8 Teams antreten.

Das geht nicht. So sieht der Spielplan für 8 Teams aus
1:2   3:4   5:6   7:8
1:3   2:4   5:7   6:8
1:4   2:3   5:8   6:7
1:5   2:5   3:6   4:8
1:6   2:7   3:8   4:5
1:7   2:8   3:5   4:6
1:8   2:6   3:7   4:3
Um es in 6 Runden abzuwickeln müssten in den ersten vier Runden jeweils
2 Teams zweimal antreten
1:2   3:4   5:6   7:8   1:8
1:3   2:4   5:7   6:8   2:6
1:4   2:3   5:8   6:7   3:7
1:5   2:5   3:6   4:8   4:3
1:6   2:7   3:8   4:5   
1:7   2:8   3:5   4:6   

gruss ekkehard