Как реализовать расписание кругового турнира?

Question

[Олег]

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

Первый тур:
home: [t0 t1 t2 t3 t4 ]
guest: [t5 t6 t7 t8 t9 ]
Второй тур:
home: [t0 t5 t1 t2 t3]
guest: [t6 t7 t8 t9 t4]
третий тур:
home: [t0 t6 t5 t1 t2]
guest: [t7 t8 t9 t4 t3]

Возможно, существут готовые решения по другому алгоритму, но я не в состоянии составить релевантный запрос в гугле.

Comments

[Андрей]

Правильно ли я понимаю, что туров должно быть (N-1)*2 - участник должен сыграть с каждым из соперников строго два раза - один раз как хозяин и один раз как гость ?

[Олег]

Андрей: Да, именно так

[Mercury13]

Требований к разработке турнира много. Главные из них…
1. Поле меняется хозяин-гость-хозяин-гость…, и должно быть как можно меньше перемен.
2. Игра идёт в два круга, и если матч А-Б идёт в 1-м круге, то матч Б-А — во втором.
Попробую.

[Mercury13]

> и должно быть как можно меньше перемен.
…как можно меньше отступлений от этого порядка (в идеале — одна на круг).

[Mercury13]

Туров будет 2(N−1) для чётного числа команд, и 2N — для нечётного.

Answer 1

[Mercury13]

Других методов я просто не вижу. Искать «round-robin tournament algorithm». Но, по-моему, проще поворачивать не кольцо, а схему матчей, поставив одну из команд (лучше последнюю) в центр круга.
https://commons.wikimedia.org/wiki/File:Round-robi...

Матчам 2-13, 3-12 и т.д. даём фиксированные направления, причём попеременно: 2-13, 12-3, 11-4…
Направление матча 1-14 постоянно меняется.

Если команды нумеруются от 0 до N−1, N — чётное, алгоритм получается такой.

trans := случайная перестановка чисел 0 … N−1

если N чётное
  то M := N−1
  иначе M := N

цикл 2half = false…true
  цикл round = 0…M−1
    цикл shift = 1…[M/2]
      home := (round + shift) % M
      away := (round + M − shift) % M
      если (shift нечётное) xor 2half
        обменять home, away
      вывести trans[home], trans[away]

    если N чётное
      home := round
      away := M
      если (round нечётное) xor 2half
        обменять home, away
      вывести trans[home], trans[away]

Для чётного N одна команда постоянно меняет поле, у остальных — единожды на круге сбивается. Для нечётного N ничего не сбивается.

Comments

[Олег]

Спасибо!
Правильно ли я понял, что этот алгоритм выводит пары соперников сразу для всех туров? и если мне необходимо написать функцию, выдающую результаты для определенного круга, то следует убрать цикл round и передать в значение round в качестве аргумента функции?

[Mercury13]

Ошибся с циклом по shift, от 1 до M/2
2half — первый круг или второй
round — номер тура

Если для одного тура, то…
1. Придётся что-то сделать с массивом trans (он общий для всех туров). Или сгенерировать на стороне, или убрать.
2. Придётся сделать функцию, которая выдаёт кол-во туров в круге — M−1.

Answer 2

[Олег]

По запросу 'Round-robin tournament algorithm' нашел всё-таки образец, который смог транслировать в JS. Вот моя реализация только для четного количества команд (для нечетного предлагается добавить в массив фантомного участника):

// На входе - массив с командами и опционально - необходимый тур
function schedule(array, round) { // если тур не указан - создаётся всё расписание целиком
    if (!round) {
        var teams = array.length,
            // точка, после которой команды будут меняться местами "дома - гость"
            halfTour = (teams - 1),
            totalRounds = halfTour * 2,
            matchesPerRound = teams / 2,
            matches = [],
            rounds = [],
            round,
            match,
            home,
            away,
            swap,
            currentRoundText;
        for (round = 0; round < totalRounds; round++) {
            currentRoundText = [(round + 1)];
            matches = [];
            for (match = 0; match < matchesPerRound; match++) {
                home = (round + match) % (teams - 1);
                away = (teams - 1 - match + round) % (teams - 1);
                if (match === 0) {
                    away = teams - 1;
                }
                if (round >= halfTour) { 
                    swap = home;
                    home = away;
                    away = swap;
                }
                currentRoundText += ('[' + array[home]+ ' ' + array[away] + ']');
                matches.push([array[home], array[away]]);
            }
            console.log(currentRoundText);
            rounds.push(matches);
        }
        return rounds;
    }
    // Если раунд указан, просчитывается весь турнир и берется нужный элемент массива
    return schedule(array)[round - 1]; 
}

Answer 3

[trurl123]

Очень понятно как реализовывать описано тут chess.sainfo.ru/tabl/tablei.html