Algorytm planowania dla turnieju round-robin?

Question

Niedawno studiowałem i spotykam się z Donaldem Knuthem. Ale nie znalazłem odpowiedniego algorytmu dla mojego problemu.

Problem Mamy ligę z graczami. co tydzień mają jeden mecz z drugim. w ciągu 1 tygodnia każda drużyna walczyła ze sobą. są n/2 mecze dziennie. ale jedna drużyna może walczyć tylko raz w tygodniu. jeśli wygenerujemy kombinację (n/k), otrzymamy wszystkie kombinacje ... (zakładając, że k = 2), ale muszę je przynieść we właściwej kolejności.

Moja pierwsza sugestia była ... nie najlepsza. Właśnie utworzyłem tablicę, a następnie pozwoliłem komputerowi spróbować, jeśli znajdzie właściwą drogę. jeśli nie, wróć do początku, przetasuj tablicę i zrób to ponownie, cóż, zaprogramowałem ją w PHP (n = 8), a co wychodzi działa, ale zajmuje dużo czasu, a dla n = 16 daje mi to timeout także.

więc pomyślałem, czy może znaleźć algorytm, czy ktoś zna książkę, która obejmuje ten problem.

A oto mój kod: http://pastebin.com/Rfm4TquY

Answer 1

klasyczny algorytm działa tak:

Liczba zespołów 1..n. (Tutaj wezmę n = 8.)

Napisz wszystkie zespoły w dwóch rzędach.

1 2 3 4 
8 7 6 5 

Kolumny pokazują, które zespoły zagrają w tej rundzie (1 vs 8, 2 vs 7, ...).

Teraz trzymaj 1 ustalony, ale obracaj wszystkie pozostałe zespoły. W 2 tygodniu, masz

1 8 2 3 
7 6 5 4 

w tygodniu 3, masz

1 7 8 2 
6 5 4 3 

ten trwa przez tydzień n-1, w tym przypadku,

1 3 4 5 
2 8 7 6 

Jeśli n jest nieparzysta , zrób to samo, ale dodaj zespół fikcyjny. Ktokolwiek jest dopasowany do zespołu manekinowego, dostaje w tym tygodniu bye.