Поиск алгоритма для сопоставления

Question

Для небольшого карточного турнира, в котором мы играем в командах (2 на 2), мне нужно составить «план» того, кто будет играть против кого.

«Правила»:

• У нас есть несколько команд, каждая из которых состоит из пары игроков.
• У нас есть несколько «раундов» в турнире.
• Количество раундов меньше, чем количество команд.

Цель состоит в том, чтобы составить план, в котором ни одна команда не сыграет дважды против другой команды.

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

Вот пример того, что я хочу для вывода, он был сгенерирован моим "тяжелым путем":

Tournament with 16 teams and 10 rounds

Round 0
Team 0 versus Team 1
Team 2 versus Team 3
Team 4 versus Team 5
Team 6 versus Team 7
Team 8 versus Team 9
Team 10 versus Team 11
Team 12 versus Team 13
Team 14 versus Team 15

Round 1
Team 0 versus Team 2
Team 1 versus Team 3
Team 4 versus Team 6
Team 5 versus Team 7
Team 8 versus Team 10
Team 9 versus Team 11
Team 12 versus Team 14
Team 13 versus Team 15

Round 2
Team 0 versus Team 3
Team 1 versus Team 2
Team 4 versus Team 7
Team 5 versus Team 6
Team 8 versus Team 11
Team 9 versus Team 10
Team 12 versus Team 15
Team 13 versus Team 14

Round 3
Team 0 versus Team 4
Team 1 versus Team 5
Team 2 versus Team 6
Team 3 versus Team 7
Team 8 versus Team 12
Team 9 versus Team 13
Team 10 versus Team 14
Team 11 versus Team 15

Round 4
Team 0 versus Team 5
Team 1 versus Team 4
Team 2 versus Team 7
Team 3 versus Team 6
Team 8 versus Team 13
Team 9 versus Team 12
Team 10 versus Team 15
Team 11 versus Team 14

Round 5
Team 0 versus Team 6
Team 1 versus Team 7
Team 2 versus Team 4
Team 3 versus Team 5
Team 8 versus Team 14
Team 9 versus Team 15
Team 10 versus Team 12
Team 11 versus Team 13

Round 6
Team 0 versus Team 7
Team 1 versus Team 6
Team 2 versus Team 5
Team 3 versus Team 4
Team 8 versus Team 15
Team 9 versus Team 14
Team 10 versus Team 13
Team 11 versus Team 12

Round 7
Team 0 versus Team 8
Team 1 versus Team 9
Team 2 versus Team 10
Team 3 versus Team 11
Team 4 versus Team 12
Team 5 versus Team 13
Team 6 versus Team 14
Team 7 versus Team 15

Round 8
Team 0 versus Team 9
Team 1 versus Team 8
Team 2 versus Team 11
Team 3 versus Team 10
Team 4 versus Team 13
Team 5 versus Team 12
Team 6 versus Team 15
Team 7 versus Team 14

Round 9
Team 0 versus Team 10
Team 1 versus Team 11
Team 2 versus Team 8
Team 3 versus Team 9
Team 4 versus Team 14
Team 5 versus Team 15
Team 6 versus Team 12
Team 7 versus Team 13

Answer 1

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

A  B  C  D
E  F  G  H

Итак, в первом раунде пары имеют вид A - E, B - F и т. Д. Затем A фиксируется, а все остальные вращаются на одну позицию по часовой стрелке:

A  E  B  C
F  G  H  D

Повторите.

Если количество раундов меньше n - 1 , я бы предложил швейцарскую систему. Вы можете выполнить спаривание вручную, но уже существует много программ спаривания, некоторые используют эвристику, некоторые - вариант алгоритма идеального соответствия минимального веса "цветущего" Эдмонда.

Answer 2

Вы можете адаптировать алгоритм сортировки выбора для генерации перестановок. Я сделал что-то подобное давно. См. Раздел «Перестановки в парах» этой статьи .

Код написан на Паскале, но должен быть достаточно простым для преобразования в C #.