贝格尔编排算法

发表于 | 分类于

贝格尔编排算法可以有效的避免多队伍比赛中上一局优胜队跟轮空队比赛的不公平现象。一般用在队伍较少、比赛周期较长的情况下。

基本规则如下：queNum为参赛队伍数量。

  1. 将所有队伍从1、2、3…开始编排。若总队伍为奇数，则增加0置于末尾。
  2. 按编号从中间分成两半，左半边从上到下书写，右半边从下到上书写，位于同一水平线的队伍进行比赛。如下。 
         1 - 0
     2 - 5
     3 - 4
  3. 在偶次轮，将0或最大数置于左上角；在奇次轮，则置于右上角。
  4. 每轮将1从上一轮的位置移动指定间隔，若遇到0则跳过不算。指定间隔 = Math.floor(queNum/2)。
  5. 当已产生不大于queNum的奇次轮，则停止。

若参赛队伍为5，即queNum = 5，举例如下：


        第一轮    第二轮     第三轮    第四轮     第五轮
        1 - 0     0 - 4     2 - 0     0 - 5     3 - 0
        2 - 5     5 - 3     3 - 1     1 - 4     4 - 2
        3 - 4     1 - 2     4 - 5     2 - 3     5 - 1

JS实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 贝格尔编排算法
let createMatches = function(queNum){
    // 轮次
    let turnNum = queNum + (queNum%2 -1); 
    // 赛制编排表
    let matches = [];  
    // 初始轮
    matches[0] = [];
    for(let i = 0; i < queNum; i++){
        matches[0].push(i+1);
    }
    if (turnNum == queNum) {
        matches[0].push(0);
    }
    let left = false;
    // 移动间隔
    var space = Math.floor(queNum / 2);
    // 后继轮次首先将最大数字或0换边
    // 再将1按照间隔移动，其余数字逆时针填写
    // 产生后继轮次
    for(let j = 1; j < turnNum ; j ++) {
        matches[j] = new Array(turnNum + 1);
        let pos = matches[j-1].indexOf(1);
        if (left) {
            matches[j][turnNum] = matches[0][turnNum];
            if (turnNum - pos > space) {
                pos--;
            }
        }else {
            matches[j][0] = matches[0][turnNum];
            if (turnNum - pos >= space) {
                pos--;
            }
        }
        left = !left;
        pos = (pos + space + 1)%(turnNum+1);
        // 是否遇到大数
        let meet = false;
        for(let i = 0; i < turnNum; i++){
            if (matches[j][(pos+i)%(turnNum+1)] === 0) {
                meet = true;
            }
            if (meet) {
                matches[j][(pos+i+1)%(turnNum+1)] = i+1;
            } else {
                matches[j][(pos+i)%(turnNum+1)] = i+1;
            }
        }
    }
    return matches;
};