Алгоритм планирования для кругового турнира?

Question

Я недавно изучал вещи и встретился с Дональдом Кнутом. Но я не нашел правильный алгоритм для моей проблемы.

Проблема У нас есть лига с n игроками. каждую неделю у них есть матч друг с другом. Через n-1 недели каждая команда сражалась друг против друга. Есть n / 2 матчей в день. но одна команда может бороться только один раз в неделю. если мы генерируем (n / k) комбинацию, мы получаем все комбинации ... (предполагая, что k = 2), но мне нужно привести их в правильном порядке.

Мое первое предложение было ... не самым лучшим. Я только что сделал массив, а затем позвольте компьютеру попробовать, если он найдет правильный путь. если нет, вернитесь к началу, перетасуйте массив и сделайте это снова, ну, я запрограммировал его на PHP (n = 8), и то, что получается, работает, но занимает много времени, а для n = 16 это дает мне тайм-аут а также.

Так что я подумал, что если мы найдем алгоритм или кто-нибудь знает книгу, посвященную этой проблеме.

А вот мой код: http://pastebin.com/Rfm4TquY

Answer 1

Классический алгоритм работает так:

Количество команд 1..n. (Здесь я возьму n = 8.)

Запишите все команды в два ряда.

1 2 3 4
8 7 6 5

В столбцах указано, какие команды будут играть в этом раунде (1 против 8, 2 против 7, ...).

Теперь оставьте 1 фиксированным, но вращайте все остальные команды. На 2 неделе вы получите

1 8 2 3
7 6 5 4

и на 3 неделе вы получите

1 7 8 2
6 5 4 3

Это продолжается до недели n-1, в данном случае

1 3 4 5
2 8 7 6

Если n нечетно, сделайте то же самое, но добавьте фиктивную команду. Тот, кто противостоит фиктивной команде, получает на этой неделе пока .