前の関連記事

📖　イロ・レーティングって何だぜ（＾～＾）？＜その２＞

情報

📖　Git Hub

はじめに

「　スイス式トーナメントのマッチングを実装しようぜ？」

「　柿木さんか　瀧澤さんか　山田さんか　カツ丼が　ソースコードを持っているのでは？」

「　ソースコード読んでも　あんたら　分かんないでしょ」

リーグ（League；総当たり）

「　スイス・システム・トーナメント（Swiss-system-tournament；スイス式トーナメント）は、
リーグ（League；総当たり）できないときに　使われる。
リーグできない理由は、人数多いとか、時間無いとか、様々だぜ」

「　じゃあ　まず　リーグのマッチングのアルゴリズムを実装してくれだぜ」

「　👆　y が 1 ～4 の人たち、ここでは偶数の人数としよう、
全員が　次の人を選んだら……」

「　👆　ペアリングは成立しないので、
偶数番の人には　正負の符号を反転してもらう必要があるな」

「　奇数と偶数で　挙動が変わるアルゴリズムなのかしらねえ？」

リーグ　２ラウンド目

「　👆　1 の代わりに 2 にしても　うまく働いたな」

「　序数　めんどくさいので　基数　にしたらどう？」

「　👆　モジュロ（modulo；法）を使う時は　序数を使った方がいいかだぜ」

「　３ラウンド目も　うまくいくのかだぜ？」

「　👆　うまく行ったが？」

「　永遠に上手くいく証明はできるの？」

ラウンド番号を序数 r とする
参加人数を yy とする。yy は偶数とする
参加者番号は基数 y とする

リーグでの対戦相手番号は

(y+yy+r)%yy    if 自分の参加者番号が偶数
(y+yy-r)%yy    if 自分の参加者番号が奇数

「　👆　この定義の証明か。何も思い浮かばんな」

「　👆　yy が 8 のとき、 r=2 で　ぐちゃぐちゃだぜ」

「　画面端でループしてるけど、
蛇の頭が　ただ伸びてるだけですもんね」

ふつうに考えて　線対称なのでは？

「　対角線を軸とした、線対称になる式にしないといけないのでは？」

「　まったくだぜ」

「　０番目の＋６と、　６番目の－６　は線対称になるのは　分かるし、
プラス方向に進むか、マイナス方向に進むかは　対角線の位置で分かる」

「　じゃあ　奇数、偶数じゃなくて　対角線を使って　分けりゃいいんじゃないの？」

「　👆　対角線で分かれているのは確かだが、
ｘについても、ｙについても、排他的でないといけないぜ」

「　色分けしてくれだぜ」

「　👆　こうだぜ」

「　これだけ　分かってって　あと何が分からないんだぜ？」

２つのグループに分けることができる

「　👆　上のグループと、下のグループは　法則が別かな？　左右反転」

「　👆　ウィンドウのようなものも　あるんじゃないの？」

「　認識しづらいな……　もっと良い補助線があるんじゃないか？」

「　👆　複利計算みたいだな……」

セル・オートマトンで何とかならないか？

「　分岐があるような計算　困難なんで
分岐が無くせないか　まず考えてみよう」

「　👆　対角線のセルに　１　が入っているとしよう」

「　👆　1 + 1 = 2 までは　すぐ行けるが……」

「　👆　足すというより、自然数の蛇が伸びているとしよう」

「　👆　行き止まりに入った 4 が居るな」

「　👆　対角線に +4 した 5 を使って　リスタートしたらどうだぜ？」

「　👆　なんか　数列ができてきたな」

「　👆　もう少し」

「　👆　乱数生成器みたいだ」

「　この数を　簡単に生成できないの？」

「　今やった　やり方を　短くできそうだな」

「　👆　最大数を足して複写だぜ」

「　その手順のステップ数を　セルに振ってくれだぜ」

「　👆　これで分かるだろ」

「　関数作れないの？　行番号と　列番号で　ステップ数が出てくる Excel の関数みたいなやつ」

「　思い浮かばなかったので、アルゴリズムでやりたい」

アルゴリズムを考える

「　👆　０ラウンド目」

「　👆　１ラウンド目」

「　👆　２ラウンド目」

「　あとは　繰り返しだぜ」

「　１６元数みたいだ」

「　実装してみましょう」

テーブル・サイズの変更

Source   Target
------   -----------
0, 1,    0, 1, 0, 1, 
1, 0,    0, 0, 0, 0,
         0, 0, 0, 0,
         0, 0, 0, 0,

「　👆　テーブルサイズを大きくすると　レイアウトが崩れるから、
４倍のテーブルは　新しく作るようにしないといけないな。
コピー中に　元の表の５倍　メモリサイズ食う」

「　ずれずに　コピーするには　どうやるんだぜ？」

Source   Target
------   ------------
0, 1,     0, 1, 2, 3, 
2, 3,     4, 5, 6, 7,
          8, 9,10,11,
         12,13,14,15,

「　👆　現状、配列のインデックスなわけだが……」

Source          Target
-------------   -----------------------------------
(0,0), (0,1),   ( 0, 0), ( 0, 1), ( 0, 2), ( 0, 3),
(1,0), (1,1),   ( 1, 0), ( 1, 1), ( 1, 2), ( 1, 3),
                ( 2, 0), ( 2, 1), ( 2, 2), ( 2, 3),
                ( 3, 0), ( 3, 1), ( 3, 2), ( 3, 3),

「　👆　(x, y) の座標形式に変換してから、同じとこへコピーする感じだな」

x = index % edge_size
y = math.floor(index / edge_size)

index = y * edge_size + x

「　👆　x, y, index の変換は上記の通りだぜ」

.