javascript - 配对锦标赛设计算法

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

您可以使用 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);