Алгоритм выбора случайных пар, расписание матчей

Question

Я работаю в Ruby, но я думаю, что этот вопрос лучше всего задает агностик языка. Можно предположить, что у нас есть доступ к основным функциям списка/массива, а также к «случайному» генератору чисел. Вот что я хотел бы быть в состоянии сделать:

Учитывая коллекцию n команд, с n даже,

1. Случайным пара каждой команды с противником, таким образом, что каждая команда является частью ровно один пара. Назовите это ROUND 1.
2. Случайным генерируют n-2 последующие раунды (ROUND 2 через ROUND n-1) таким образом, что:
   • Каждый раунд обладает тем же свойством, что и первый (каждая команда является членом одной пары), а
   • После всех раундов, каждая команда столкнулась с любой другой командой ровно один раз.

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

Answer 1

Я верю Вы описываете round robin tournament. Страница wikipedia дает алгоритм.

Если Вам нужен способ рандомизации расписания, рандомизации порядок команды, круглый заказ и т.д.

Answer 2

Ну не уверен, что это наиболее эффективный алгоритм, но:

1. Случайным назначить N команд в два списка одинаковой длины п/2 (List1, List2)
2. Начиная с I = 0:
3. Создание пары: List1 [I], List2 [I] = а команда пары

4. Повтор для г = 1-> (п/2-1)

   для раундов 2-> п/2-1 :

5. Поверните List2, так что первая команда в List2 теперь находится в конце.
6. Повторите шаги с 2 по 5 до тех пор, пока List2 не будет циклически включен один раз.

Answer 3

Эта ссылка была очень полезной для меня в последний раз, когда я написал алгоритм циклического планирования. Он включает реализацию C первого алгоритма соответствия для циклических спариваний.

http://www.devenezia.com/downloads/round-robin/

В дополнение к алгоритму, он имеет некоторые полезные ссылки на другие аспекты турнира планирования (балансировочные дома и на выезде игры, а также вращающиеся команды по полям/судов).

Обратите внимание, что во всех случаях вам не обязательно нужен «случайный» порядок. Если, например, вы планировали круговую футбольную лигу для 8 игр, в которой было только 6 команд, то каждой команде придется дважды играть в две команды. Если вы хотите сделать более приятный сезон для всех, вы должны начать беспокоиться о посеве, чтобы у вас не было двух лучших команд, которые сражались за две самые слабые команды в последних двух играх. Вам было бы лучше организовать дополнительные игры, которые будут объединены с командами с аналогичной силой/посевом.

Answer 4

На основе информации я нашел через Maniek-х link, я пошел со следующим:

1. A простой циклический алгоритм, который

   a. Начинается с спаривания, достигнутого записями [0,...,(n-1)/2] и [(n-1)/2 + 1,..., n-1]. (Таким образом, если n==10 мы 0 в паре с 5, 1 с 6 и т.д.)

   б. Поворачивает всех, кроме одной команды, n-2 раза по часовой стрелке, пока все команды не сыграют друг с другом. (Итак, в раунде 2 мы соединяем 1 с 6, 5 с 7 и т. Д.)

2. Произвольно назначает одну из [0,..., n-1] каждой из команд.