[Algorytmy] Wyznaczenie kolejek meczowych

[L24]

Witam! Mam spory problem z ustawieniem zawodników w kolejkach meczowych. O co chodzi? Już wyjaśniam:

W sezonie gra parzysta liczba graczy. Liczba par meczowych jakie możemy z nich utworzyć jest \(\displaystyle{ \frac{n}{2}}\) . Sezon dzieli się na \(\displaystyle{ n-1}\) kolejek oraz na \(\displaystyle{ n-1}\) kolejek rewanżowych. W każdej kolejce grają wszyscy gracze, jeden na jeden (tworzą wspomniane pary). Chodzi o to by mógł zagrać każdy z każdym, żeby w \(\displaystyle{ n-1}\) kolejkach (bez rewanżów) każdy mecz wystąpił tylko raz (1 kontra 2 to to samo co: 2 kontra 1, więc odpada), oraz że w jednej kolejce żaden z graczy nie zagra dwa razy.

Przykład dla \(\displaystyle{ n=6}\):

\(\displaystyle{ G=\left\{ 1,2,3,4,5,6\right\}}\)
Mamy 6 graczy czyli 5 kolejek (bez rewanżów):

\(\displaystyle{ 1vs2}\)
\(\displaystyle{ 3vs4}\)
\(\displaystyle{ 5vs6}\)

\(\displaystyle{ 13}\)
\(\displaystyle{ 25}\)
\(\displaystyle{ 46}\)

\(\displaystyle{ 14}\)
\(\displaystyle{ 26}\)
\(\displaystyle{ 35}\)

\(\displaystyle{ 15}\)
\(\displaystyle{ 24}\)
\(\displaystyle{ 36}\)

\(\displaystyle{ 16}\)
\(\displaystyle{ 23}\)
\(\displaystyle{ 45}\)

Jak widać każda kolejka ma unikalne mecze.
Napisałem program w C++ który wyznacza takie kolejki. Problem w tym że jego złożoność jest liniowa, i jak dla \(\displaystyle{ 6!}\) daje jeszcze radę, tak dla \(\displaystyle{ 20!}\) komputer się poddaje.
Jest może jakiś szybszy sposób na wyznaczanie tego typu kolejek meczowych? Może jest ktoś zorientowany w tym jak to wygląda np. w takiej angielskiej Barclays Premier League? Tam jest 20 zespołów, każdy gra z każdym i jest 38 kolejek (z rewanżowymi). W jaki sposób stworzyć taki terminarz?

Byłbym bardzo wdzięczny za pomoc i wskazówki!
Pozdrawiam.

[Jacek_Karwatka]

Problem który przedstawiasz to kolorowanie krawędziowe grafu pełnego.
Wierzchołki grafu to drużyny. Krawędzie to mecze do rozegrania. Kolor krawędzi to terminy spotkań.
Zła wiadomość jest taka że ogólny problem kolorowania grafu jest problemem NP - zupełnym. Nie są znane wielomianowe algorytmy które dają zawsze rozwiązanie optymalne (minimalną liczbę kolorów).
Dobra jest taka że Twój graf jest grafem pełnym o parzystej liczbie wierzchołków. To dosyć specyficzny graf i jego indeks chromatyczny jest równy 2n-1.
Myślę że są duże szanse aby znaleźć konkretny algorytm pod hasłem kolorowanie krawędziowe grafu.
Dwa algorytmy heurystyczne są znane jako NTL i NC

[marcin_smu]

Oczywiście że istnieją, proste algorytmy tworzenia takich lig. Np. w tym artykule jest jakieś opisany

Kod: Zaznacz cały

http://www.deltami.edu.pl/temat/informatyka/algorytmy/2011/02/27/O_rozgrywkach_ligowych

Jest chyba nawet nietrudny do zaimplementowania.