问题描述
我正在尝试构建一个Javascript函数作为输入:
I'm trying to build a Javascript function that takes as an input:
- 一组玩家，例如
["player1"，"player2"，"player3"，"player4"](可能只有相等数量的玩家)
并根据以下规则动态创建锦标赛设计数组:
and dynamically creates an array for a tournament design based on the following rules:
- 每个玩家与同一位玩家的合作伙伴不超过一次
- 每个玩家的比赛总数相等
输出将是一个包含匹配数组的数组，每个数组包含四个条目，例如[玩家1，玩家2，玩家3，玩家4]代表玩家1和玩家2与玩家3和玩家4.
the outputs would be an array containing arrays of matches with four entries each e.g. [player1, player2, player3, player4] stands for player1 and player2 vs. player3 and player4.
[["player1","player2","player3","player4"], ["player1","player3","player2","player4"], ...]
目前，我使用类似以下示例的方法进行硬编码，但不幸的是，仅适用于预定义数量的玩家.
Currently I use something like the below example to do this hard-coded but unfortunately only for a pre-defined number of players.
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;
每一个提示都会感谢！
欢呼
推荐答案
您可以使用回合-robin锦标赛机制来配对玩家.在每次迭代中，除一个玩家外，所有玩家都将替换下一个玩家.如果玩家数量为奇数，将有一名玩家被排除在比赛之外，但每次迭代中将有一名不同的玩家.由于游戏需要2对，因此可能有一对都不参与.同样，在每次迭代中这将是不同的对.
You could use the round-robin tournament mechanism to pair players. At each iteration all players, except one, take the place of the next player. If the number of players is odd, there will be one player excluded from matching, but it will be a different one in each iteration. As a game needs 2 pairs, there might be a pair that is not participating either. Again, this will be a different pair in each iteration.
此方法将使每个玩家玩的游戏次数与其他玩家一样多，除非玩家人数是2模4(即6、10、14，...).在这种情况下，除一个人外，所有其他人都将玩相同数量的游戏.杰出的玩家将再玩2场游戏.
This method will make each player play as many games as the other players, except for when the number of players is 2 modulo 4 (i.e. 6, 10, 14, ...). In that case all players except one will play the same number of games. The exceptional player will play 2 more games.
为 n 位玩家找到的游戏数量以及每位玩家的游戏数量将遵循以下公式:
The number of games found for n players, and the number of games per player, will follow this formula:
#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个游戏.
Example: given 16 players, the algorithm will find 60 games, where each player gets to play in 15 games.
这是一个实现:
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);这篇关于双人比赛设计算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！