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

js algorithm 羽毛球 八人转

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

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

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

按照上面的思路，用js实现的算法如下：

//组合可能的搭档/组队
function combo(N) {
    let pairs = []
    for (let a = 1; a <= N; a++) {//从1开始，好看一些
        for (let b = a + 1; b <= N; b++) {
            pairs.push([a, b, 0])//a和b搭档:[a, b, 上场次数]
        }
    }
    return pairs
}
function isConflict(A, B) {//判断两个组队人员是否冲突
    return A == B || A[0] == B[0] || A[0] == B[1] || A[1] == B[0] || A[1] == B[1]
}
//匹配可能的对局
function match(pairs) {
    let vs = [], P = pairs.length
    for (let i = 0; i < P; i++) {
        let A = pairs[i]
        for (let j = i + 1; j < P; j++) {
            let B = pairs[j]
            if (isConflict(A, B)) continue//跳过冲突的对局
            vs.push([A, B])//A队和B队对局/对打v:[A,B]
        }
    }
    return vs
}
//N人转，至少打M局的对阵编排
//公平轮转：每人和其他人都搭档一次，每队至少上场一次，各人轮换上场，每人上场次数要相同
function main(N, M) {
    if (N < 4) return console.error(`人数不足(${N}<4)`)
    if (N > 20) return console.error(`人数太多啦！`)
    let plays = new Array(N).fill(0)//记录玩家上场次数
    function tires(v) {//计算候选对局的疲劳度（需进一步优化，见后面改写为类的代码）
        let A = v[0], B = v[1]
        return (A[2] + 1) * (plays[A[0] - 1] + plays[A[1] - 1]) + (plays[B[0] - 1] + plays[B[1] - 1]) * (B[2] + 1)
    }
    let pairs = combo(N)//获取可能的组队
    let allvs = match(pairs)//获取所有的对局
    let vs = []//对阵上场次序数组
    console.log(`${N}人，${pairs.length}队，${M>0?('打'+M+'局'):''}对阵：`)
    for (let i = 0; allvs.length > 0 ; i++) {
        let v = allvs.shift()//取第一对上场
        let A = v[0], B = v[1]//更新对阵参与者
        A[2]++, plays[A[0] - 1]++, plays[A[1] - 1]++
        B[2]++, plays[B[0] - 1]++, plays[B[1] - 1]++
        console.log(`${i + 1}. (${A[0]},${A[1]}) x (${B[0]},${B[1]})`)
        vs.push(v)
        if (!M || i+1 >= M){
            if (pairs.every(p => p[2]>0)){//每队都上场过
                if (plays.every(c => c==plays[0])) break//每人上场次数都一样
            }
        }
        allvs = allvs.sort((a, b) => tires(a) - tires(b))//把最少上场的排到第一位
    }
    console.log(`每人上场${plays[0]}次.\n`)
    return vs
}
// 试一下
main(3),main(4),main(5)
main(6),main(6, 15)
main(7),main(7, 21)
main(8),main(8, 16),main(8, 18)
main(9),main(9, 27)
main(10),main(100)

改写成一个类：

//N人转对阵编排
//公平轮转：每人和其他人都组队搭档一次，两队轮流上场PK，最后每人上场次数相同即可输赢按积分排名
class CMatch {
    #N      //参赛人数
    #users  //记录每人上场次数
    #pairs  //所有2人搭档组合
    #fours  //所有2x2对局
    vs      //对阵顺序数组
    constructor(N) {
        this.#N = N;
    }
    play(M) {//至少M局的对阵编排，不指定M则按最少局数编排
        const N = this.#N
        if (N < 4) return console.error(`人数不足(${N}<4)`)
        if (N > 20) return console.error(`人数太多啦！`)
        let users = this.#genUsers(true)//重置每人上场次数
        let pairs = this.#genPairs(true)//获取可能的组队
        let fours = this.#genAllvs(true)//获取所有的对局
        let vs = this.vs = []//对阵上场次序数组
        console.log(`${N}人，组${pairs.length}队，${M > 0 ? ('打' + M + '局') : ''}对阵：`)
        M = M || pairs.length/2 //默认至少两两对阵
        for (; fours.length > 0;) {
            vs.push(fours.shift())//取第一对上场
            this.#updateUsers(vs)
            // if (vs.length >= Math.ceil(N*N/4 - N/4)) break;
            if (vs.length >= M) {//每队都上场过 //if (pairs.every(p => p[2]>0)) 
                if (users.every(c => c == users[0])) {//每人上场次数一样
                    break;
                }
            }
            fours.forEach(v => this.#calcTires(v))//更新每队的疲劳度
            fours = fours.sort((v1, v2) => v1[2] - v2[2])//把最少上场的排到第一位
        }
        let noplays = pairs.filter(p => !p[2])
        if (noplays && noplays.length){
            console.log(`有${noplays.length}队没有上场：`, JSON.stringify(noplays))
        }
        if (users.every(c => c == users[0])) {
            console.log(`每人上场${users[0]}次。\n`)
        } else {
            console.log(JSON.stringify(users), `每人上场次数不完全一样。\n`)
        }
        return this
    }
    #genUsers(reset) {//生成每人上场次数数组
        if (!this.#users) {
            this.#users = new Array(this.#N).fill(0)
        } else if (reset) {
            this.#users.fill(0)
        }
        return this.#users
    }
    #genPairs(reset) {//可能的搭档组合
        const N = this.#N
        if (!this.#pairs) {
            this.#pairs = []
            for (let a = 1; a <= N; a++) {//从1开始，好看一些
                for (let b = a + 1; b <= N; b++) {
                    this.#pairs.push([a, b, 0])//a和b搭档:[a, b, 上场次数]
                }
            }
        } else if (reset) {
            this.#pairs.forEach(p => p[2] = 0)//重置上场次数
        }
        return this.#pairs
    }
    #genAllvs(reset) {//可能的对局
        if (!this.#fours || reset) {
            this.#fours = []
            let pairs = this.#pairs, P = pairs.length
            for (let i = 0; i < P; i++) {
                let A = pairs[i]
                for (let j = i + 1; j < P; j++) {
                    let B = pairs[j]
                    if (CMatch.#isConflict(A, B)) continue//跳过冲突的对局
                    this.#fours.push([A, B])//A队和B队对局/对打v:[A,B]
                    // if (c++ > 10) break
                }
            }
        }
        return this.#fours
    }
    #updateUsers(vs) {//更新对阵成员上场次数
        let i = vs.length, v = vs[i-1]
        let A = v[0], B = v[1]
        let up = A => {this.#users[A[0] - 1]++, this.#users[A[1] - 1]++, A[2]++}
        up(A), up(B)
        console.log(`${i}. (${A[0]},${A[1]}) x (${B[0]},${B[1]})`)//打印对阵表记录
    }
    #calcTires(v) {//计算候选对局的疲劳度
        let users = this.#users, vs = this.vs
        let A = v[0], B = v[1]
        let ca = A => {//上场次数增加疲劳程度
            let a = users[A[0] - 1], b = users[A[1] - 1]
            return A[2]*(a + b) + a*b
        }
        let tires = CMatch.#isRecombo(v, vs[vs.length-1])//累计疲劳度
        vs.forEach((s, i) => CMatch.#isRecombo(v, s)>=4 ? (tires += i + 4) : null)//四人重组上场，+i使靠后的场次值变大，避免连续上场
        let ta = ca(A), tb = ca(B)
        tires += ta + tb + Math.abs(ta-tb) + Math.sqrt(ta*tb)
        return v[2] = tires
    }
    static #isConflict(A, B) {//判断两个组队人员对局是否冲突
        return A === B || A[0] == B[0] || A[0] == B[1] || A[1] == B[0] || A[1] == B[1]
    }
    static #isRecombo(v1, v2) {//两队是4人重组？
        if (v1 === v2) return 4
        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)
    }
    static #inVS(a, v) {//a是否在v场？
        return (v[0][0] == a) || (v[0][1] == a) || (v[1][0] == a) || (v[1][1] == a)
    }
}
// 测试
new CMatch(4).play()
new CMatch(5).play()
new CMatch(6).play()
new CMatch(7).play().play(21)
new CMatch(8).play().play(16).play(18)
new CMatch(9).play().play(27)
new CMatch(10).play()