循环算法在 Javascript 中表现异常

Round robin algorithm behaving strangely in Javascript

提问人:Kristoffer Andersson 提问时间:11/17/2023 最后编辑:isherwoodKristoffer Andersson 更新时间:11/21/2023 访问量:72

问:

我正在制定一个程序,目标是为锦标赛(网球双打)制定时间表。以下是它应该如何工作:

  • 我提供了包含球员和比赛时间的函数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>

JavaScript 算法 循环

评论


答:

0赞 Barmar 11/18/2023 #1

分配给法院的循环不会在每个时间段分配给多个法院。每次通过循环时,您都会进入下一个时间段。

对时间段和法院使用索引变量,您可以分别递增。当法院索引达到该时隙的长度时,将递增时隙索引。

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>

评论

0赞 Kristoffer Andersson 11/20/2023
谢谢,但这也产生了一个有缺陷的时间表。如果您检查版本的输出,在上周(2024-02-26)只安排了 4 场比赛。第一周有 6 场比赛按预期安排。我也遇到了这个问题,我搞不清原因。非常感谢您的帮助
0赞 Scott Sauyet 11/20/2023 #2

我没有尝试理解和修复您的代码。不好意思。相反,我试图自己解决问题。这是我的尝试。


维基百科上描述了一个简单的算法,我们固定一个玩家,然后通过网格旋转其余的玩家(在奇数的情况下使用一个虚拟玩家;面对这个虚拟玩家的玩家在回合中轮空。⌈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 只是创建结果的字符串版本以显示到控制台的一种方式。

评论

1赞 Kristoffer Andersson 11/21/2023
非常感谢,我将你的代码与我的代码结合使用,现在它可以工作了..!:)