Создание расписания партий по круговой системе Laravel
Всем привет! Я создаю систему управления соревнованиями на laravel. Я получаю участников группы с помощью отношения Group::competitors, и у меня есть таблица партий personal_games, в которой есть поля player1 и player2 для id участников. Мне нужно написать функцию контроллера PersonalGameController, которая бы создавала партии по круговой системе по следующим схемам:
Для группы из 3 игроков:
1 тур: 2-3
2 тур: 3-1
3 тур: 1-2
Для группы из 4 игроков:
1 тур: 1-4, 2-3
2 тур: 3-1, 2-4
3 тур: 1-2, 4-3
Для группы из 5 игроков:
1 тур: 2-4, 1-5
2 тур: 4-1, 5-3
3 тур: 1-3, 2-5
4 тур: 3-2, 5-4
5 тур: 1-2, 3-4
Для группы из 6 игроков:
1 тур: 2-4, 1-5, 3-6
2 тур: 4-1, 6-2, 5-3
3 тур: 1-3, 2-5, 4-6
4 тур: 3-2, 6-1, 5-4
5 тур: 1-2, 3-4, 5-6
Вот таблицы БД (для понимания):
competitors:
personal_games (результаты пока не заполняются, там null)
Помогите, пожалуйста, придумать алгоритм, который бы выдавал партии по таким схемам. В идеале хотелось бы, чтобы он работал и для другого количества участников в группе. Заранее всем благодарен!
Ответы (1 шт):
Можно использовать round-robin алгоритм генерации всех пар.
Для иллюстрации - располагаем элементы в два ряда. Если нечётное количество - добавляем фиктивного, играющий с ним отдыхает.
Фиксируем один элемент A
На каждом круге циклически сдвигаем все элементы, кроме фиксированного, образуем новые пары
A B
D C
-----
A D
C B
----
A C
B D
Пары:
AD, BC
AC, BD
AB, CD
P.S.
О, я даже на PHP что-то такое изображал, для нечётного количества в комментариях дополнение.
Пример на Python, для нечетного количества участников играющий с последним (фиктивным) отдыхает