トーナメントの組み合わせ

　必要になったときにサッと用意できるように、もとい暇つぶしとして、トーナメントの組み合わせを作成するプログラムを考えてみる。
　(作成したスクリプトなどを置く場所を作った。https://github.com/nkknj/magimenalmirai)
　まず参加者名簿のようなものをエクセルで作成した。(sample.xlsx)

　　チーム名：チーム名
　　チームランク：全参加チームの中でのチームとしての順位、団体戦の成績とか
　　選手名：選手名
　　チーム内ランク：その選手のチームの中での順位
　　前年度ランク：前年度のランク保持者はその成績を記入

　まずこの参加者名簿から全選手の順位付けを行う。方針として、
(1)前年度ランク保持者はそれに基づいて昇順で先頭に並べる
(2)チームごとの参加者人数で調整したチーム内ランクで昇順に並べる
(3)調整チーム内ランクが同率の場合、チームランクで昇順に並べる
のようにする。

-----------------------------------------------------------------------

import sys
import numpy as np
import pandas as pd

filename=sys.argv[1]
df=pd.read_excel(filename)

#ランク保持者のみ抽出
df=df.sort_values(by=["前年度ランク"], ascending=True)
rank=df[df["前年度ランク"]>=0]

#ランク非保持者のみ抽出
temp=df[~(df["前年度ランク"]>=0)]
temp=temp.reset_index(drop=True)

#ランク非保持者の調整チーム内ランクを計算
K=np.zeros(temp.shape[0])
for i in range(K.shape[0]):
    K[i]=np.sum(df['チーム名']==temp['チーム名'][i])

temp['チーム内ランク']=temp['チーム内ランク']/K

#ソート
temp=temp.sort_values(by=["チーム内ランク", "チームランク"], ascending=True)

#ランク保持、非保持を結合
rank=pd.concat([rank, temp])

rank=rank.reset_index(drop=True)
rank.index+=1
rank.to_excel('rank_'+filename)

-----------------------------------------------------------------------

　これで参加者名簿から全体の順位付けが完了。(rank_sample.xlsx)
　次にトーナメントの位置決め。紙に書いていくように「端、端、内、内」と埋めていくのを実装するのは非常に面倒臭そうだったので、逆に数字を挿入して広げていく方式をとることにした。具体的には、[1, 4, 3, 2]となっている数列を最初に作った後、先頭から奇数コ目の後ろにゼロを2個ずつ挿入し、のちに2n, 2n+1番目の和が2^k+1になるような数をゼロに代入していく。2^kからの端数は、その端数を超える最小の2^kを求めて、不要な要素の削除、およびbyeとして0を代入する。

-----------------------------------------------------------------------
N=rank.shape[0]
position=np.array([1, 4, 3, 2])
#まずは参加者数を超える最小の2^kの数までの並び順
p1=2
while N>pow(2, p1):
    i=0
    while i<pow(2, p1-1):
        position=np.r_[position[:4*i+1], np.zeros(2), position[4*i+1:]]
        i+=1
       
    i=0
    while i<pow(2, p1):
        if position[2*i]==0:
            position[2*i]=pow(2, p1+1)+1-position[2*i+1]
        else:
            position[2*i+1]=pow(2, p1+1)+1-position[2*i]
        i+=1   
    p1+=1
   
p2=1
while N-pow(2, p1-1)>pow(2, p2):
    p2+=1
   
position=position[position<=pow(2, p1-1)+pow(2, p2)]
position[position>N]=0
print(position)
print(p2)

-----------------------------------------------------------------------

[ 1. 65. 64. 33. 32. 17. 48. 49.  0. 16.  9. 73. 56. 41. 24. 25. 40. 57.
72.  8.  5. 69. 60. 37. 28. 21. 44. 53. 76. 12. 13. 77. 52. 45. 20. 29.
36. 61. 68.  4.  3. 67. 62. 35. 30. 19. 46. 51.  0. 14. 11. 75. 54. 43.
22. 27. 38. 59. 70.  6.  7. 71. 58. 39. 26. 23. 42. 55. 74. 10. 15.  0.
50. 47. 18. 31. 34. 63. 66.  2.]
4

　最後に表示させているp2が4なので、2^4=16番までの下には1回戦があり、その他は全て2回戦スタート。
　この数列と、上で求めた全体の順位を対応させればいいのだが、ではここからトーナメント表を描くとなるとこれはpythonでやるのはとても大変そうである。ググったところturtleというもので再帰的にトーナメントを描くことができるようだが、1回戦の有無などを反映させるのは厳しそう。他にpythonでエクセルの枠線扱えた気がするけど、これも実装やばそうなので却下。つまり表に落とし込むにはエクセルポチポチかね。

　ところで、経験的に第1シード下の1回戦がbyeになっている印象なのだが、上の方法だとN-pow(2, p1-1)~pow(2, p2)番目の横の1回戦のところにbyeが来るんよね。試しに全国公のトーナメント表を眺めてみたら、第1シード下の中シード横の1回戦にbyeがあるので、これは上記と同じ方法をとっていそうである。なのでまぁ、この辺はローカルルールなんかね。