Algorithmus zur Berechnung von Spieltagen im Sport.

Fischkopf2009

Hallo .
Ich habe folgendes Problem. Ich will ein Programm schreiben, was mir aus einer Liste von Mannschaften einen Spielplan berechnet / bzw erstellt.
Dabei ist aber folgendes zu beachten. Es spielen nicht immer 2 Mannschaften sondern 3.

Also folgendes Beispiel.
Team1 - Team2
Team1 - Team3
Team2 - Team3

Das wäre ein Spieltag.

HAt jeamnd eine Idee wie man das realisieren kann. Ich will keinen Quellcode sondern nur eine idee

VIelen Dank

Bashar

Im Prinzip suchst du aus einer Menge von n Mannschaften alle 3-elementigen Teilmengen, um dann daraus einen Spieltag zu basteln. Das kann man so machen:

for i = 1 to n
  for j = i+1 to n
    for k = j+1 to n
      team i -- team j
      team i -- team k
      team k -- team j

Hier ist die Bedingung, dass immer 3 Teams spielen und in welcher Reihenfolge sie untereinander die Spiele austragen, festcodiert. Wenn man das variabel halten will, wird es komplizierter.

Spieltag bedeutet doch normalerweise: Alle spielen jeden Spieltag und nach n Spieltagen haben Alle gegen Alle gespielt. Im Vergleich zum "normalen Spieltag" z.b. in der Bundesliga kenne ich noch die Variation, das z.b. 8 Mannschaften in der Liga sind, und jetzt treffen sich davon 3 Mannschaften, nochmal 3 Mannschaften und 2 Mannschaften. Die Dreiergruppen machen 3 Spiele und die Zweiergruppe nur 1. Das spart Fahrtkosten aber kann Mannschaften bzgl. Heimspielen benachteiligen.

Ausser Bruteforce kenne ich allerdings auch keinen Algorithmus dafuer.

Fischkopf2009

Bashar schrieb:

Im Prinzip suchst du aus einer Menge von n Mannschaften alle 3-elementigen Teilmengen, um dann daraus einen Spieltag zu basteln. Das kann man so machen:
for i = 1 to n
  for j = i+1 to n
    for k = j+1 to n
      team i -- team j
      team i -- team k
      team k -- team j
Hier ist die Bedingung, dass immer 3 Teams spielen und in welcher Reihenfolge sie untereinander die Spiele austragen, festcodiert. Wenn man das variabel halten will, wird es komplizierter.

Das stimmt aber nicht weil dann jede Mannschaft öfter als nur einmal gegeneinander spielen

Team1 - Team2
Team1 - Team3
Team2 - Team3

Team1- TEam3
Team1 - Team4
Team3 - Team4

usw.

Bashar

Gibts noch mehr Zusatzbedingungen, die zu erwähnen du vergessen hast?

Fischkopf2009

Nein - das ist alles. Ich dachte das wäre logisch für einen Spielplan

Also jede Mannschaft spielt an genau einem Spieltag, habe ich das richtig verstanden?

Sei n := 3k die Anzahl der Teams,
m die Anzahl der Spiele pro Tag,
T := < t_0, ..., t_n > die Sequenz der Teams
i := 1

solange i <= n:
   M := < >
   für j := i bis i + (m - 1):
       M := M [e]upsilon[/e] T[j]

   Ermittle alle zweistelligen Permutationen aus M
   Gib diese aus

   i := i + m