配对锦标赛设计算法

Question

我正在尝试构建一个 Javascript 函数作为输入：

一组玩家，例如["player1","player2","player3","player4"] （可能只有相同数量的玩家）

并根据以下规则为锦标赛设计动态创建数组：

每个玩家与同一个玩家合作的次数不超过一次
每个玩家的总匹配数相等

输出将是一个包含匹配数组的数组，每个匹配项有四个条目，例如[player1, player2, player3, player4]代表player1和player2对player3和player4。

[["player1","player2","player3","player4"], ["player1","player3","player2","player4"], ...]

目前我使用类似于下面的示例来进行此硬编码，但不幸的是仅适用于预定义数量的玩家。

const m = [];

const A = players[0];
const B = players[1];
const C = players[2];
const D = players[3];
const E = players[4];
const F = players[5];
const G = players[6];
const H = players[7];
const I = players[8];
const J = players[9];
const K = players[10];
const L = players[11];
const M = players[12];
const N = players[13];
const O = players[14];
const P = players[15];

m.push(A, B, C, P);
m.push(A, C, E, O);
m.push(B, C, D, A);
m.push(B, D, F, P);
m.push(C, D, E, B);
m.push(C, E, G, A);
m.push(D, E, F, C);
m.push(D, F, H, B);
m.push(E, F, G, D);
m.push(E, G, I, C);
m.push(F, G, H, E);
m.push(F, H, J, D);
m.push(G, H, I, F);
m.push(G, I, K, E);
m.push(H, I, J, G);
m.push(H, J, L, F);
m.push(I, J, K, H);
m.push(I, K, M, G);
m.push(J, K, L, I);
m.push(J, L, N, H);
m.push(K, L, M, J);
m.push(K, M, O, I);
m.push(L, M, N, K);
m.push(L, N, P, J);
m.push(M, N, O, L);
m.push(M, O, A, K);
m.push(N, O, P, M);
m.push(N, P, B, L);
m.push(O, P, A, N);
m.push(O, A, C, M);
m.push(P, A, B, O);
m.push(P, B, D, N);

return m;

感谢您的每一个提示！

干杯

Answer 1

您可以采用组合算法检查所需结果的四的长度。

function getTournament(array, size) {

    function fork(i, t) {
        if (t.length === size) {
            result.push(t);
            return;
        }
        if (i === array.length) {
            return;
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }

    var result = [];
    fork(0, []);
    return result;
}

console.log(getTournament([1, 2, 3, 4, 5, 6], 4).map(function (a) { return JSON.stringify(a); }));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

存在相当简单round-robin tournament algorithm

将玩家设置成两排。固定第一个玩家位置。写入当前对（行之间）。如果玩家人数为奇数，则其中一名玩家在每轮比赛中休息。

下一轮循环换人。再写对。重复

A B
D C 
-----      pairs A-D, B-C
A D
C B
----
A C
B D

Answer 3

假设我对问题的理解是正确的，如果您的玩家数量为奇数，这没有解决方案。

注意：每对只出现一次（意味着如果你在前两个位置有 a 和 b，或者在第三和第四个位置，那将是唯一的情况，即使前两个位置可能恰好有 a和 b 在第 3/4 或反之亦然）
我们有 n-1 + n-2 + ... + 2 + 1 对 n(n-1) / 2
我们希望每场比赛有 2 对情侣 => 比赛数量将为 n(n-1) / 4
一旦我们建立了对（这很容易做到），我们就想混合它们；为此，我们创建了一个函数，给定一对夫妇和一组夫妇，returns 数组中符合要求的第一对夫妇（只是不同的人）。
请注意，我们已经知道匹配项的数量，因此我们可以迭代该固定次数。
作为最后一步，我们要将这对夫妇合并到 4 条目数组中。

这是代码，

const players = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L'];
let couples = [];
for (let i = 0; i < players.length; i++) {
    for (let j = i + 1; j < players.length; j++) {
        couples.push([players[i], players[j]]);
    }
}
console.log(couples.length === (players.length * (players.length - 1)) / 2); // true

function findFirstAvailableCouple(couple, arr) {
    for (let i = 0; i < arr.length; i++) {
        if (couple.indexOf(arr[i][0]) === -1 && couple.indexOf(arr[i][1]) === -1) {
            const ret = arr.splice(i, 1)[0];
            return ret;
        }
    }
}
let matches = [];
const n = couples.length / 2;
for (let i = 0; i < n; i++) { const current = couples.splice(0, 1)[0];
    matches.push([current, findFirstAvailableCouple(current, couples)]);
}
matches = matches.map(e => [...e[0], ...e[1]]);
console.log(matches);

您可以在控制台查看结果。

这个算法可以适用于情侣/玩家的任意数量的条目（随着成本的增加）

Answer 4

您好，您可以尝试使用以下代码。

function getUniquePairArray(_arr) {
    var _tArr = [];
    for(var i = 0; i < _arr.length; i++) {
        for(var j = i+1; j < _arr.length; j++) {
            _tArr.push([_arr[i],_arr[j]]);
        }   
    } 
    return _tArr;
}

以上代码将从数组中创建唯一的对。例如输入

[1,2,3,4]

输出

[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

var findOne = function (haystack, arr) {
    return arr.some(function (v) {
        return haystack.indexOf(v) >= 0;
    });
};

以上函数检查给定数组中目标数组中存在的每个元素。

function finalResult(_arr) {
    var _tArr = [];
    for(var i = 0; i < _arr.length; i++) {
        for(var j = i+1; j < _arr.length; j++) {
            if(!findOne(_arr[i],_arr[j]))
            {
                _tArr.push([_arr[i],_arr[j]]);
                break;
            }
        }   
    } 
    return _tArr;
}

此函数将为您提供所需的输出。

INPUT == finalFun(getUniquePairArray(["p1","p2","p3","p4","p5"]))

OUTPUT = "[p1,p2,p3,p4][p1,p3,p2,p4][p1,p4,p2,p3][p1,p5,p2,p3][p2,p3,p4 ,p5][p2,p4,p3,p5][p2,p5,p3,p4]

Answer 5

您可以使用 round-robin tournament 机制来配对玩家。在每次迭代中，除一个玩家外，所有玩家都会取代下一个玩家。如果玩家数量为奇数，则会有一名玩家被排除在匹配之外，但每次迭代都是不同的。由于一个游戏需要 2 对，因此可能有一对也没有参与。同样，这将是每次迭代中的不同对。

此方法将使每个玩家与其他玩家玩同样多的游戏，但玩家数量为 2 模 4 时除外（即 6、10、14 等）。在这种情况下，除一个玩家外，所有玩家都将玩相同数量的游戏。杰出的球员将再打2场比赛。

为 n 名玩家找到的游戏数量，以及每位玩家的游戏数量，将遵循以下公式：

#players(n) modulo 4  |   #games             |  #games per player
----------------------+----------------------+--------------------
        0             | n(n-1)/4             |       n-1
        1             | n(n-1)/4             |       n-1
        2             | (n-1)(n-2)/4         |       n-3 (one: n-1)    
        3             | floor((n-1)(n-2)/4)  |       n-3

示例：给定 16 名玩家，算法将找到 60 场比赛，其中每位玩家可以参加 15 场比赛。

这是一个实现：

function assignToGames(players) {
    // Round the number of players up to nearest multiple of 2.
    // The potential extra player is a dummy, and the games they play 
    //   will not be included.
    const numPlayers = players.length + players.length % 2, // potential dummy added
        pairsPerRound = numPlayers / 2,
        rotatingPlayers = numPlayers - 1,
        firstRound = players.length % 2, // will make the dummy game being ignored 
        games = [];
    
    for (let round = 0; round < rotatingPlayers; round++) {
        for (let i = firstRound; i < pairsPerRound-1; i+=2) {
            // The following formulas reflect a roundrobin scheme, where
            //   the last player (possibly a dummy) does not move.
            games.push([
                players[i ? (i+round-1) % rotatingPlayers : numPlayers - 1],
                players[(numPlayers-i-2+round) % rotatingPlayers],
                players[(i+round) % rotatingPlayers],
                players[(numPlayers-i-3+round) % rotatingPlayers],
            ]);
        }
    }
    return games;
}

// Optional function to test the correctness of the result, 
//    and count the number of games per player:
function getStatistics(players, games) {
    const usedPairs = new Set(),
        stats = Object.assign(...players.map( player => ({ [player]: 0 }) ));
    
    for (let game of games) {
        // verify uniqueness of pairs
        for (let pairIndex = 0; pairIndex < 4; pairIndex += 2) {
            let pair = JSON.stringify(game.slice(pairIndex,pairIndex+2).sort());
            if (usedPairs.has(pair)) throw "Duplicate pair " + pair;
            usedPairs.add(pair);
        }
    }
    // Count the number of games each player plays:
    for (let i = 0; i < games.length; i++) {
        for (let j = 0; j < 4; j++) {
            stats[games[i][j]]++;
        }
    }
    return stats;
}

// Demo
// Create 16 players. Their values are the letters of the alphabet up to "p". 
const players = Array.from("abcdefghijklmnop");
const games = assignToGames(players);
// Display results
console.log(JSON.stringify(games));
console.log("--- statistics ---");
console.log('#games: ', games.length);
const stats = getStatistics(players, games);
console.log(stats);

配对锦标赛设计算法

Pair-Tournament design algorithm

javascript

arrays

algorithm

math

combinatorics