Формирование уникальных пар из массива

Question

Всем привет. Помогите пожалуйста решить проблему.

Имеется массив чисел const arr = [1, 2, 3, 4, 5, 6] (массив всегда будет четный). Также имеется n абстрактных туров, в каждом туре есть (arr.length / 2) матчей

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

Пара [1,2] и [2,1] являются одинаковым

Валидный пример:

const arr = [1,2,3,4]

result:
Тур1 -> [[1,2], [3,4]]
Тур2 ->[[1,3], [2,4]]
Тур3 ->[[1,4], [2,3]]

Невалидный пример:

const arr = [1,2,3,4]

result:
Тур1 -> [[1,2], [3,4]]
Тур2 ->[[1,3], [2,4]]
Тур3 ->[[3,4], [2,3]]

Answer 1

Алгоритм round-robin позволяет сгенерировать все туры, гарантируя, что каждый играет с каждым, и пары не повторяются. Проверять при этом ничего не нужно.

Записываем массив в две строки, создаём пары соответственных элементов.

1  2  3
|  |  |  
4  5  6    //1 тур

пары 1-4, 2-5, 3-6

Фиксируем первый элемент, а остальные циклически сдвигаем (физически массив вертеть не нужно, достаточно использовать сдвиг индексов)

1  4  2
5  6  3     //2 тур
---------
1  5  4
6  3  2
---------
1  6  5
3  2  4
---------
1  3  6
2  4  5
---------

Таки образом, получено n-1 туров, в которых (n-1)*n/2 матчей разных пар

PHP, Python, ещё Python, JS можно на EnSO поискать

Answer 2

В свое время реализовывал roud-robin алгоритм на C#.

/// Приложение выполняет турнирную генерацию круговой
/// системы встреч для n команд. Кол-во ЧЕТНОЕ!
/// 
/// Кол-во туров: n - 1. Кол-во игр в каждом туре: n / 2.
/// 
/// Генерация выполняется путем фиксации первой команды 
/// и последующего поворота по часовой стрелке последней
/// команды.
/// 
/// Пары генерируются следующим образом: 1 vs n, 2 vs n - 1, 
/// 3 vs n - 2 и т.д.
/// 
/// Пример для четырех команд. 
/// Список команд: 1, 2, 3, 4.
/// Первый тур: 1 vs 4, 2 vs 3.
/// Поворачиваем по часовой стрелке крайний элемент:
/// => 1, 4, 2, 3.
/// Второй тур: 1 vs 3, 4 vs 2.
/// Поворачиваем по часовой стрелке крайний элемент:
/// => 1, 3, 4, 2
/// Третий тур: 1 vs 2, 3 vs 4.

static (int teamOne, int teamTwo)[][] RoundRobinGenerator(int n)
{
    var teams = Enumerable.Range(1, n);
    var rounds = Enumerable.Range(0, n - 1).Select(round => teams.Take(1).Concat(teams.TakeLast(round)).Concat(teams.Skip(1).SkipLast(round)).ToArray());
    var roundGenerator = rounds.Select(round => Enumerable.Range(0, round.Length / 2).Select(team => (round[team], round[^(team + 1)])).ToArray()).ToArray();

    return roundGenerator;
}

var roundRobin = RoundRobinGenerator(8);
for (int i = 0; i < roundRobin.Length; i++)
{
    Console.Write($"{i + 1, 2:d} тур: ");
    for (int j = 0; j < roundRobin[i].Length; j++)
    {
        Console.Write($"{roundRobin[i][j].teamOne}-{roundRobin[i][j].teamTwo}" + " ");
    }
    Console.WriteLine();
}

Результат для n = 8:

 1 тур: 1-8 2-7 3-6 4-5
 2 тур: 1-7 8-6 2-5 3-4
 3 тур: 1-6 7-5 8-4 2-3
 4 тур: 1-5 6-4 7-3 8-2
 5 тур: 1-4 5-3 6-2 7-8
 6 тур: 1-3 4-2 5-8 6-7
 7 тур: 1-2 3-8 4-7 5-6

Answer 3

function generateRounds(arr) {
    const totalPairs = (arr.length / 2);
    const rounds = [];
    const usedPairs = new Set();

    function isPairUnique(pair) {
        const [a, b] = pair;
        return !usedPairs.has(`${a}-${b}`) && !usedPairs.has(`${b}-${a}`);
    }

    function addPairsToUsed(pairs) {
        pairs.forEach(pair => {
            const [a, b] = pair;
            usedPairs.add(`${a}-${b}`);
            usedPairs.add(`${b}-${a}`);
        });
    }

    function generateRound() {
        const available = [...arr];
        const roundPairs = [];

        while (roundPairs.length < totalPairs) {
            let pair = [];
            let foundUniquePair = false;

            while (!foundUniquePair && available.length > 1) {
                const player1 = available.splice(Math.floor(Math.random() * available.length), 1)[0];
                const player2 = available.splice(Math.floor(Math.random() * available.length), 1)[0];
                pair = [player1, player2];

                if (isPairUnique(pair)) {
                    roundPairs.push(pair);
                    foundUniquePair = true;
                } else {
                    available.push(player1, player2); // вернуть элементы для новой попытки
                }
            }

            if (!foundUniquePair) return null; // если не удалось собрать уникальную пару, тур невалиден
        }

        addPairsToUsed(roundPairs);
        return roundPairs;
    }

    while (true) {
        const round = generateRound();
        if (!round) break; // если не удалось собрать уникальный тур, завершаем
        rounds.push(round);
        if (rounds.length === arr.length - 1) break; // остановка, если все возможные туры были собраны
    }

    return rounds;
}

const arr = [1, 2, 3, 4];
const result = generateRounds(arr);
result.forEach((round, index) => {
    console.log(`Тур${index + 1} ->`, round);
});

Answer 4

Великолепный ответ MBo объясняет как устроен Round-Robin. Оказывается его не сложно реализовать через арифметику по модулю:

const tournament = n => {
    const t = [];
    for (let k = 0; k < n - 1; ++k) {
        const r = [[1, n - k]];
        const b = 2 * n - k - 3;
        for (let m = 1; m < n / 2; ++m) {
            r.push([2 + (b + m) % (n - 1), 2 + (b - m) % (n - 1)]);
        }
        t.push(r);
    }
    return t;
};

БЛОГ НА HUSL

Формирование уникальных пар из массива

Ответы (4 шт):