js实现羽毛球比赛中的八人转和多人转 - zhouted/zhouted.github.io GitHub Wiki

标签： 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人转对阵编排
class CMatch {
    #N      //人数
    #plays  //每人上场次数
    #pairs  //所有搭档组合
    #allvs  //所有可能对局

    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 plays = this.#genPlays(true)//每人上场次数
        let pairs = this.#genPairs(true)//获取可能的组队
        let allvs = this.#genAllvs(true)//获取所有的对局
        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]//更新对阵参与者
            this.#updatePlay(A)
            this.#updatePlay(B)
            vs.push(v)
            console.log(`${i + 1}. (${A[0]},${A[1]}) x (${B[0]},${B[1]})`)
            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) => this.#calcTires(a) - this.#calcTires(b))//把最少上场的排到第一位
        }
        console.log(`每人上场${plays[0]}次。\n`)
        return this
    }

    #genPlays(reset) {//生成每人上场次数数组
        if (!this.#plays){
            this.#plays = new Array(this.#N).fill(0)
        }else if (reset){
            this.#plays.fill(0)
        }
        return this.#plays
    }

    #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.#allvs || reset){
            this.#allvs = []
            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.#allvs.push([A, B, 0])//A队和B队对局/对打v:[A,B,上场次数,比?分?]
                }
            }
        }
        return this.#allvs
    }

    #updatePlay(A) {//累加A队上场次数
        this.#plays[A[0]-1]++, this.#plays[A[1] - 1]++, A[2]++
    }

    #calcTires(v) {//计算候选对局的疲劳度
        let A = v[0], B = v[1], plays = this.#plays
        return (A[2] + 1) * (plays[A[0] - 1] + plays[A[1] - 1]) + (plays[B[0] - 1] + plays[B[1] - 1]) * (B[2] + 1)
    }

    static #isConflict(A, B) {//判断两个组队人员对局是否冲突
        return A == B || A[0] == B[0] || A[0] == B[1] || A[1] == B[0] || A[1] == B[1]
    }

}

// 测试
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()