[关闭]
@TedZhou 2023-04-18T10:13:21.000000Z 字数 4698 阅读 152

js实现羽毛球比赛中的八人转和多人转

js algorithm 羽毛球 八人转


羽毛球爱好者熟知的八人转,就是N个人轮转进行双打比赛,大家的机会均等、比较公平。一轮打下来的输赢积分较能客观反映实际。

八人转基本规则就是:每人和其他人都组队搭档一次,每队至少上场一次,各人轮换上场,每人上场次数要相同。

编程实现N人转对阵编排的算法思路:
1. 找出所有的组队,即N个人中取2人的组合C
2. 所有组队两两对阵比赛,即C组队中取2对的组合,但要去除人员冲突的对阵(自己不能和自己打),剩下的对阵仍然可能太多,人多了不可能都打一遍
3. 为了公平轮换,只要找上场最少的人和队优先打即可
4. 每队都上场一次后,每人上场次数一样时就可以结束轮转,也可以继续打更多局,但总要在每人上场次数一样时结束。

按照上面的思路,用js实现的算法如下:

  1. //组合可能的搭档/组队
  2. function combo(N) {
  3. let pairs = []
  4. for (let a = 1; a <= N; a++) {//从1开始,好看一些
  5. for (let b = a + 1; b <= N; b++) {
  6. pairs.push([a, b, 0])//a和b搭档:[a, b, 上场次数]
  7. }
  8. }
  9. return pairs
  10. }
  11. function isConflict(A, B) {//判断两个组队人员是否冲突
  12. return A == B || A[0] == B[0] || A[0] == B[1] || A[1] == B[0] || A[1] == B[1]
  13. }
  14. //匹配可能的对局
  15. function match(pairs) {
  16. let vs = [], P = pairs.length
  17. for (let i = 0; i < P; i++) {
  18. let A = pairs[i]
  19. for (let j = i + 1; j < P; j++) {
  20. let B = pairs[j]
  21. if (isConflict(A, B)) continue//跳过冲突的对局
  22. vs.push([A, B])//A队和B队对局/对打v:[A,B]
  23. }
  24. }
  25. return vs
  26. }
  27. //N人转,至少打M局的对阵编排
  28. //公平轮转:每人和其他人都搭档一次,每队至少上场一次,各人轮换上场,每人上场次数要相同
  29. function main(N, M) {
  30. if (N < 4) return console.error(`人数不足(${N}<4)`)
  31. if (N > 20) return console.error(`人数太多啦!`)
  32. let plays = new Array(N).fill(0)//记录玩家上场次数
  33. function tires(v) {//计算候选对局的疲劳度(需进一步优化,见后面改写为类的代码)
  34. let A = v[0], B = v[1]
  35. return (A[2] + 1) * (plays[A[0] - 1] + plays[A[1] - 1]) + (plays[B[0] - 1] + plays[B[1] - 1]) * (B[2] + 1)
  36. }
  37. let pairs = combo(N)//获取可能的组队
  38. let allvs = match(pairs)//获取所有的对局
  39. let vs = []//对阵上场次序数组
  40. console.log(`${N}人,${pairs.length}队,${M>0?('打'+M+'局'):''}对阵:`)
  41. for (let i = 0; allvs.length > 0 ; i++) {
  42. let v = allvs.shift()//取第一对上场
  43. let A = v[0], B = v[1]//更新对阵参与者
  44. A[2]++, plays[A[0] - 1]++, plays[A[1] - 1]++
  45. B[2]++, plays[B[0] - 1]++, plays[B[1] - 1]++
  46. console.log(`${i + 1}. (${A[0]},${A[1]}) x (${B[0]},${B[1]})`)
  47. vs.push(v)
  48. if (!M || i+1 >= M){
  49. if (pairs.every(p => p[2]>0)){//每队都上场过
  50. if (plays.every(c => c==plays[0])) break//每人上场次数都一样
  51. }
  52. }
  53. allvs = allvs.sort((a, b) => tires(a) - tires(b))//把最少上场的排到第一位
  54. }
  55. console.log(`每人上场${plays[0]}次.\n`)
  56. return vs
  57. }
  58. // 试一下
  59. main(3),main(4),main(5)
  60. main(6),main(6, 15)
  61. main(7),main(7, 21)
  62. main(8),main(8, 16),main(8, 18)
  63. main(9),main(9, 27)
  64. main(10),main(100)

改写成一个类:

  1. //N人转对阵编排
  2. //公平轮转:每人和其他人都组队搭档一次,两队轮流上场PK,最后每人上场次数相同即可输赢按积分排名
  3. class CMatch {
  4. #N //参赛人数
  5. #users //记录每人上场次数
  6. #pairs //所有2人搭档组合
  7. #fours //所有2x2对局
  8. vs //对阵顺序数组
  9. constructor(N) {
  10. this.#N = N;
  11. }
  12. play(M) {//至少M局的对阵编排,不指定M则按最少局数编排
  13. const N = this.#N
  14. if (N < 4) return console.error(`人数不足(${N}<4)`)
  15. if (N > 20) return console.error(`人数太多啦!`)
  16. let users = this.#genUsers(true)//重置每人上场次数
  17. let pairs = this.#genPairs(true)//获取可能的组队
  18. let fours = this.#genAllvs(true)//获取所有的对局
  19. let vs = this.vs = []//对阵上场次序数组
  20. console.log(`${N}人,组${pairs.length}队,${M > 0 ? ('打' + M + '局') : ''}对阵:`)
  21. M = M || pairs.length/2 //默认至少两两对阵
  22. for (; fours.length > 0;) {
  23. vs.push(fours.shift())//取第一对上场
  24. this.#updateUsers(vs)
  25. // if (vs.length >= Math.ceil(N*N/4 - N/4)) break;
  26. if (vs.length >= M) {//每队都上场过 //if (pairs.every(p => p[2]>0))
  27. if (users.every(c => c == users[0])) {//每人上场次数一样
  28. break;
  29. }
  30. }
  31. fours.forEach(v => this.#calcTires(v))//更新每队的疲劳度
  32. fours = fours.sort((v1, v2) => v1[2] - v2[2])//把最少上场的排到第一位
  33. }
  34. let noplays = pairs.filter(p => !p[2])
  35. if (noplays && noplays.length){
  36. console.log(`有${noplays.length}队没有上场:`, JSON.stringify(noplays))
  37. }
  38. if (users.every(c => c == users[0])) {
  39. console.log(`每人上场${users[0]}次。\n`)
  40. } else {
  41. console.log(JSON.stringify(users), `每人上场次数不完全一样。\n`)
  42. }
  43. return this
  44. }
  45. #genUsers(reset) {//生成每人上场次数数组
  46. if (!this.#users) {
  47. this.#users = new Array(this.#N).fill(0)
  48. } else if (reset) {
  49. this.#users.fill(0)
  50. }
  51. return this.#users
  52. }
  53. #genPairs(reset) {//可能的搭档组合
  54. const N = this.#N
  55. if (!this.#pairs) {
  56. this.#pairs = []
  57. for (let a = 1; a <= N; a++) {//从1开始,好看一些
  58. for (let b = a + 1; b <= N; b++) {
  59. this.#pairs.push([a, b, 0])//a和b搭档:[a, b, 上场次数]
  60. }
  61. }
  62. } else if (reset) {
  63. this.#pairs.forEach(p => p[2] = 0)//重置上场次数
  64. }
  65. return this.#pairs
  66. }
  67. #genAllvs(reset) {//可能的对局
  68. if (!this.#fours || reset) {
  69. this.#fours = []
  70. let pairs = this.#pairs, P = pairs.length
  71. for (let i = 0; i < P; i++) {
  72. let A = pairs[i]
  73. for (let j = i + 1; j < P; j++) {
  74. let B = pairs[j]
  75. if (CMatch.#isConflict(A, B)) continue//跳过冲突的对局
  76. this.#fours.push([A, B])//A队和B队对局/对打v:[A,B]
  77. // if (c++ > 10) break
  78. }
  79. }
  80. }
  81. return this.#fours
  82. }
  83. #updateUsers(vs) {//更新对阵成员上场次数
  84. let i = vs.length, v = vs[i-1]
  85. let A = v[0], B = v[1]
  86. let up = A => {this.#users[A[0] - 1]++, this.#users[A[1] - 1]++, A[2]++}
  87. up(A), up(B)
  88. console.log(`${i}. (${A[0]},${A[1]}) x (${B[0]},${B[1]})`)//打印对阵表记录
  89. }
  90. #calcTires(v) {//计算候选对局的疲劳度
  91. let users = this.#users, vs = this.vs
  92. let A = v[0], B = v[1]
  93. let ca = A => {//上场次数增加疲劳程度
  94. let a = users[A[0] - 1], b = users[A[1] - 1]
  95. return A[2]*(a + b) + a*b
  96. }
  97. let tires = CMatch.#isRecombo(v, vs[vs.length-1])//累计疲劳度
  98. vs.forEach((s, i) => CMatch.#isRecombo(v, s)>=4 ? (tires += i + 4) : null)//四人重组上场,+i使靠后的场次值变大,避免连续上场
  99. let ta = ca(A), tb = ca(B)
  100. tires += ta + tb + Math.abs(ta-tb) + Math.sqrt(ta*tb)
  101. return v[2] = tires
  102. }
  103. static #isConflict(A, B) {//判断两个组队人员对局是否冲突
  104. return A === B || A[0] == B[0] || A[0] == B[1] || A[1] == B[0] || A[1] == B[1]
  105. }
  106. static #isRecombo(v1, v2) {//两队是4人重组?
  107. if (v1 === v2) return 4
  108. return CMatch.#inVS(v1[0][0], v2) + CMatch.#inVS(v1[0][1], v2) + CMatch.#inVS(v1[1][0], v2) + CMatch.#inVS(v1[1][1], v2)
  109. }
  110. static #inVS(a, v) {//a是否在v场?
  111. return (v[0][0] == a) || (v[0][1] == a) || (v[1][0] == a) || (v[1][1] == a)
  112. }
  113. }
  114. // 测试
  115. new CMatch(4).play()
  116. new CMatch(5).play()
  117. new CMatch(6).play()
  118. new CMatch(7).play().play(21)
  119. new CMatch(8).play().play(16).play(18)
  120. new CMatch(9).play().play(27)
  121. new CMatch(10).play()
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注