提问人:Kristoffer Andersson 提问时间:11/17/2023 最后编辑:isherwoodKristoffer Andersson 更新时间:11/21/2023 访问量:72
循环算法在 Javascript 中表现异常
Round robin algorithm behaving strangely in Javascript
问:
我正在制定一个程序,目标是为锦标赛(网球双打)制定时间表。以下是它应该如何工作:
- 我提供了包含球员和比赛时间的函数roundData(见下文)
- 一支球队每周只能打一次比赛
- 每场比赛都是独一无二的,这意味着A队只能与B队交手一次。
此函数成功生成 66 个匹配项,但除此之外还有错误。它没有正确分配球场,在前 3 周之后,由于某种原因,它开始制作只有 4 场比赛的几周。
我非常感谢对此的任何意见,因为我被困住了。我也找不到任何这方面的例子。谢谢!
我本来以为会得到一个每周 11 节课和总共 66 场比赛的时间表。我得到了 66 场比赛,但 15 周,因为该函数并不总是在一周内放置 6 场比赛。
function generateRoundRobinSchedule(roundData) {
let teams = roundData.teams;
let scheduleInfo = roundData.schedule;
let allMatches = [];
// Create all unique matches
for (let i = 0; i < teams.length; i++) {
for (let j = i + 1; j < teams.length; j++) {
allMatches.push({
team1: i,
team2: j
});
}
}
// Helper function to add days to a date
function addDays(dateStr, days) {
const date = new Date(dateStr);
date.setDate(date.getDate() + days);
return date.toISOString().split('T')[0];
}
// Initialize variables for scheduling
let matchSchedule = [];
let currentDate = scheduleInfo.start_date;
const timeslots = scheduleInfo.timeslots;
const matchesPerWeek = timeslots.reduce((acc, slot) => acc + slot.courts.length, 0);
// Schedule matches
while (allMatches.length > 0) {
let weeklyMatches = [];
let teamsPlayedThisWeek = new Set();
for (let match of allMatches) {
if (!teamsPlayedThisWeek.has(match.team1) && !teamsPlayedThisWeek.has(match.team2)) {
weeklyMatches.push(match);
teamsPlayedThisWeek.add(match.team1);
teamsPlayedThisWeek.add(match.team2);
}
if (weeklyMatches.length === matchesPerWeek) {
break;
}
}
// Remove scheduled matches from allMatches
allMatches = allMatches.filter(match => !weeklyMatches.includes(match));
// Assign timeslots and courts to weekly matches
let timeslotIndex = 0;
for (let match of weeklyMatches) {
const timeslot = timeslots[timeslotIndex % timeslots.length];
const court = timeslot.courts[timeslotIndex / timeslots.length % timeslot.courts.length >> 0];
matchSchedule.push({
team1: teams[match.team1],
team2: teams[match.team2],
date: currentDate,
time: timeslot.time,
court: court,
duration: scheduleInfo.match_length
});
timeslotIndex++;
}
// Prepare for next week
currentDate = addDays(currentDate, 7);
}
console.log(matchSchedule)
return matchSchedule;
}
generateRoundRobinSchedule(roundData);
<script>
const roundData = {
"teams": [
{ "player1_email": "1", "player2_email": "2" },
{ "player1_email": "3", "player2_email": "4" },
{ "player1_email": "5", "player2_email": "6" },
{ "player1_email": "7", "player2_email": "8" },
{ "player1_email": "9", "player2_email": "10" },
{ "player1_email": "11", "player2_email": "12" },
{ "player1_email": "13", "player2_email": "14" },
{ "player1_email": "15", "player2_email": "16" },
{ "player1_email": "17", "player2_email": "18" },
{ "player1_email": "19", "player2_email": "20" },
{ "player1_email": "21", "player2_email": "22" },
{ "player1_email": "23", "player2_email": "24" }
],
"schedule": {
"start_date": "2023-11-20",
"days": ["Monday"],
"timeslots": [
{ "time": "18:30", "courts": ["Court 1", "Court 2"] },
{ "time": "19:00", "courts": ["Court 4"] },
{ "time": "20:00", "courts": ["Court 1", "Court 2"] },
{ "time": "20:30", "courts": ["Court 4"] }
],
"match_length": 90
}
}
</script>
答:
分配给法院的循环不会在每个时间段分配给多个法院。每次通过循环时,您都会进入下一个时间段。
对时间段和法院使用索引变量,您可以分别递增。当法院索引达到该时隙的长度时,将递增时隙索引。
function generateRoundRobinSchedule(roundData) {
let teams = roundData.teams;
let scheduleInfo = roundData.schedule;
let allMatches = [];
// Create all unique matches
for (let i = 0; i < teams.length; i++) {
for (let j = i + 1; j < teams.length; j++) {
allMatches.push({
team1: i,
team2: j
});
}
}
// Helper function to add days to a date
function addDays(dateStr, days) {
const date = new Date(dateStr);
date.setDate(date.getDate() + days);
return date.toISOString().split('T')[0];
}
// Initialize variables for scheduling
let matchSchedule = [];
let currentDate = scheduleInfo.start_date;
const timeslots = scheduleInfo.timeslots;
const matchesPerWeek = timeslots.reduce((acc, slot) => acc + slot.courts.length, 0);
// Schedule matches
while (allMatches.length > 0) {
let weeklyMatches = [];
let teamsPlayedThisWeek = new Set();
for (let match of allMatches) {
if (!teamsPlayedThisWeek.has(match.team1) && !teamsPlayedThisWeek.has(match.team2)) {
weeklyMatches.push(match);
teamsPlayedThisWeek.add(match.team1);
teamsPlayedThisWeek.add(match.team2);
}
if (weeklyMatches.length === matchesPerWeek) {
break;
}
}
// Remove scheduled matches from allMatches
allMatches = allMatches.filter(match => !weeklyMatches.includes(match));
// Assign timeslots and courts to weekly matches
let timeslotIndex = 0;
let courtIndex = 0;
for (let match of weeklyMatches) {
const timeslot = timeslots[timeslotIndex];
const court = timeslot.courts[courtIndex];
matchSchedule.push({
team1: teams[match.team1],
team2: teams[match.team2],
date: currentDate,
time: timeslot.time,
court: court,
duration: scheduleInfo.match_length
});
courtIndex++;
if (courtIndex >= timeslot.courts.length) {
courtIndex = 0;
timeslotIndex++;
if (timeslotIndex >= timeslots.length) {
timeslotIndex = 0;
}
}
}
// Prepare for next week
currentDate = addDays(currentDate, 7);
}
console.log(matchSchedule)
return matchSchedule;
}
generateRoundRobinSchedule(roundData);
<script>
const roundData = {
"teams": [
{ "player1_email": "1", "player2_email": "2" },
{ "player1_email": "3", "player2_email": "4" },
{ "player1_email": "5", "player2_email": "6" },
{ "player1_email": "7", "player2_email": "8" },
{ "player1_email": "9", "player2_email": "10" },
{ "player1_email": "11", "player2_email": "12" },
{ "player1_email": "13", "player2_email": "14" },
{ "player1_email": "15", "player2_email": "16" },
{ "player1_email": "17", "player2_email": "18" },
{ "player1_email": "19", "player2_email": "20" },
{ "player1_email": "21", "player2_email": "22" },
{ "player1_email": "23", "player2_email": "24" }
],
"schedule": {
"start_date": "2023-11-20",
"days": ["Monday"],
"timeslots": [
{ "time": "18:30", "courts": ["Court 1", "Court 2"] },
{ "time": "19:00", "courts": ["Court 4"] },
{ "time": "20:00", "courts": ["Court 1", "Court 2"] },
{ "time": "20:30", "courts": ["Court 4"] }
],
"match_length": 90
}
}
</script>
评论
我没有尝试理解和修复您的代码。不好意思。相反,我试图自己解决问题。这是我的尝试。
维基百科上描述了一个简单的算法,我们固定一个玩家,然后通过网格旋转其余的玩家(在奇数的情况下使用一个虚拟玩家;面对这个虚拟玩家的玩家在回合中轮空。⌈n/2⌉x 2
这段代码做到了这一点,并尝试将游戏分散在不同的场地/时间段,并分散出哪个玩家首先列出。(我认为这对网球来说并不重要。在国际象棋中,它将决定谁拥有白色棋子,因此先走。
结果是一个回合数组。每一轮都有一系列的场地。(这里还包括时间段。在网格中的每个位置上都有两个竞争对手的阵列(在你的情况下是双打团队)。
const rotate = (n, xs) => [
...xs.slice(xs.length - (n % xs.length)),
...xs.slice(0, xs.length - (n % xs.length))
]
const BYE = Symbol()
const roundRobin = (ts, all = ts .concat (ts .length % 2 == 0 ? [] : [BYE]), rest = all.slice(0, -1)) =>
rest
.map ((_, i) => rotate (i + 1, fold([...rotate (i, rest), all.at(-1)])))
.map(b => b.filter(([a, b]) => a !== BYE && b !== BYE))
.map((b, i) => i % 2 == 0 ? b : b.map(([a, b]) => [b, a]))
const fold = xs =>
xs.slice(0, Math.ceil(xs.length / 2)) .map ((x, i) => [x, xs[xs.length - i - 1]])
//----------------------------------------------------------------------
// (Disposable) code to log results to console
const display = sched => ` \\ Venue/Time
\\ ${sched[0].map((_, i) => String(i + 1).padStart(4, ' ')).join('')}
Round +-----------------------
${sched.map((r, i) => String(i + 1).padStart(5, ' ') + ' | ' + r.map(([a, b]) => a + b).join(' ')).join('\n')}`
console.log(display(roundRobin([...'ABCDEFGHIJKL'])))
.as-console-wrapper {max-height: 100% !important; top: 0}
我们在这里用字母来代表团队;但您可以简单地使用您的团队对象。我们不会尝试将此处的场地映射到您的位置/时间段。这应该很容易做到。
代码
rotate
:是一个简单的可重用实用程序函数,用于将数组位置旋转到右侧:n
rotate (2, ['A', 'B', 'C', 'D', 'E', 'F', 'G']) ==> ['F', 'G', 'A', 'B', 'C', 'D', 'E']
它将换行,因此可以是任何正整数
n
再见
只是一个使数字正常工作的虚拟团队。在初始名单中面对的球队将在该轮轮空。虽然我在这里删除了这些比赛,但我们同样可以保留它们,并在每一轮显示特定的轮空。BYE
roundRobin
是主要功能。它实现了圆算法。它还尝试轮换回合,以在一定程度上平衡第一或第二名单以及每个场地的出场次数。它在这方面的成功喜忧参半,我们可能会重新审视这两个因素。fold
是一个辅助函数,用于将列表 like 转换为两列,如下所示:['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
A H B G C F D E
它返回
[['A', 'H'], ['B', 'G'], ['C', 'F'], ['D', 'E']]
display
只是创建结果的字符串版本以显示到控制台的一种方式。
评论