feat: 予選試合表生成のアルゴリズム

[tufusa]

予選試合表生成のアルゴリズム

満たすべき性質はnotionを参照のこと。

例

コースが3つ、

• クラブA: A1~A4
• クラブB: B1~B3
• クラブC: C1~C2
• 無所属N: N1~N2

の合計11チームの場合

コース1左	コース1右	コース2左	コース2右	コース3左	コース3右
A1	B3	A2	C1	A3	C2
A4	N1	B1	N2	B2
B3	A1	C1	A2		A3
N1	A4	N2	B1	C2	B2

アルゴリズム

1. チームをクラブ名でソートする

   [A1, A2, A3, A4, B1, B2, B3, C1, C2, N1, N2]

2. コース数でスライスする
   表の左コース側に、左上から詰めていくことに相当する

   [A1, A2, A3],
   [A4, B1, B2],
   [B3, C1, C2],
   [N1, N2]

3. 転置する
   各コースの左側をまとめることに相当する

   [A1, A4, B3, N1],
   [A2, B1, C1, N2],
   [A3, B2, C2]

4. 各配列から右側のコースを走る相手を決める
   • 原則、そのコースで走行するチーム数の半分(切り捨て)だけ前後を循環させて後ろにずらす

     [0, 1, 2, 3] → [2, 3, 0, 1] (後ろに2だけ前後を循環させてずらす)
     → [[0, 2],
     [1, 3],
     [2, 0],
     [3, 1]] (全チーム間に1試合空いているので合法)

   • チーム数が3以下の場合、ただずらしただけでは試合が連続するチームが現れる
   • そのため、空を挿入する(=1人試合を作る)ことで試合が連続しないようにする
     • チーム数が3の場合

       [0, 1, 2] → [2, 0, 1] (後ろに1だけ前後を循環させてずらす)
       → 空を挿入
       → [[0, 2],
       [1, φ],
       [φ, 0],
       [2, 1]] (全チーム間に1試合空いているので合法)

       合法になるのはこの挿入の仕方しか存在しない。

     • チーム数が2の場合

       [0, 1] → [1, 0]
       → 空を挿入
       → [[0, 1],
       [φ, φ]
       [1, 0]]

       同じ相手とマッチしてしまうが、間に時間があることのほうを優先するため。
       実際にこのような状況になった場合はコース数を減らすべき。

     • チーム数が1の場合

       [0] → [0]
       → 空を挿入
       → [[0, φ],
       [φ, φ]
       [φ, 0]]

       間に時間があることを優先するため。
       実際にこのような状況になった場合はコース数を減らすべき。

   • 以上の操作をmakePairs関数(仮名)とし、各配列にmakePairs関数を適用する

     [[A1, B3], [A4, N1], [B3, A1], [N1, A4]],
     [[A2, C1], [B1, N2], [C1, A2], [N2, B1]],
     [[A3, C2], [B2,  φ], [ φ, A3], [C2, B2]]

     以上で完成。

[tufusa]

適当につつくなり同意を表明するなり質問するなりしてください。