配对竞赛设计算法

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

您可以使用循环赛机制对播放器进行配对。在每一次迭代中，除一位外，所有玩家都将取代下一位玩家。如果玩家的数量是奇数，那么就会有一个玩家被排除在匹配之外，但是在每次迭代中都会有一个不同的玩家。由于一个游戏需要2对，可能有一对也没有参与。同样，在每次迭代中，这将是一个不同的对。

这种方法将使每个玩家玩的游戏与其他玩家一样多，除非玩家数为2模4(即6，10，14，…)。在这种情况下，除一人外，所有玩家都将玩同样数量的游戏。这位出色的球员将再玩两场比赛。

为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);

​

Answer 2

您可以采取一个组合算法，检查4的长度，以获得想要的结果。

​

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 3

存在着相当简单的循环竞赛算法

把球员排成两排。确定第一个玩家的位置。写入电流对(行之间)。如果有多少球员是奇数，他们中的一人，在每一轮休息。

为下一轮轮班球员的循环方式。再写成对。重复

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