主页 / 问题 / 1597918
Accepted
Jonny SerB
Asked:2024-10-27 02:08:27 +0000 UTC2024-10-27 02:08:27 +0000 UTC

从数组中形成唯一对

  • 772

大家好。请帮我解决问题。

有一个数字数组 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]]
javascript

4 个回答

  1. Best Answer

    循环算法允许生成所有回合，确保每个人都玩每个人并且配对不会重复。无需检查任何东西。

    我们将数组写成两行并创建相应元素对。

    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上找到

    • 4

  2. 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;
};
    • 0

  3. 有一次我用 C# 实现了 round-robin 算法。

    /// Приложение выполняет турнирную генерацию круговой
/// системы встреч для 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
    • -1 
  4. 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);
});
    • -1

相关问题