スモールワールドネス計算時にERグラフを何個作るか

　スモールワールドネス(以後SW)は次式で定義される。

　　SW=(Cnet/Crand)/(Lnet/Lrand)
　　　Cnet: 扱っているネットワークのクラスター係数
　　　Crand: 扱っているネットワークと同じパラメタを持つERグラフのクラスター係数
　　　Lnet: 扱っているネットワークの平均最短距離長
　　　Lrand: 扱っているネットワークと同じパラメタを持つERグラフの平均最短経路長
　　　ERグラフ：Erdos-Renyi modelにより作られるネットワーク(ノード数nとリンク率p)

　Crand, Lrandが解析的に求められれば良いのだが不明。全通りの平均を求めれば確実だが、ノード数が多いと現実的な時間では終わらない。そのためErdos-Renyi modelでランダムネットワークを複数個作成してCとLを求め、その平均を用いることになる。
　では一体何個の平均をとればよいのか。
　まず1例をみてみる。個人的にこの先の未来で扱うデータはノード数10～100個程度ではないかと思うので、ひとまずノード数は80個としてみる。リンク率はとりあえずの0.5。比較するERグラフは100個でいいや。(適当)

-----------------------------------------------
import numpy as np
import matplotlib.pyplot as plt
import scipy.stats
inf=np.inf

def shortest_path_length(lengthmat):
    n=lengthmat.shape[0]
    shortest_path_length=np.zeros((n, n))
    for i_start_node in range(n):
        i_length=np.zeros(n)+inf
        candidate=np.zeros(n)+inf
        candidate[i_start_node]=0
       
        while np.min(candidate)!=inf:
            i_length[np.argmin(candidate)]=np.min(candidate)
            candidate=i_length.reshape(n, 1)+lengthmat
            candidate=np.min(candidate, axis=0)
            candidate[i_length!=inf]=inf
       
        shortest_path_length[i_start_node]=i_length
       
    return shortest_path_length

def characteristic_path_length(lengthmat, glo=True):
    n=lengthmat.shape[0]
    shortest_path_length_mat=shortest_path_length(lengthmat)
    characteristic_path_length=np.sum(shortest_path_length_mat, axis=0)/(n-1)
   
    if glo==True:
        characteristic_path_length=np.mean(characteristic_path_length)
       
    return characteristic_path_length

def clustering_coefficient(weightedmat, glo=True):
    triangles=triangle(weightedmat)
    k=np.sum(wei2unwei(weightedmat), axis=0)
    k*=(k-1)
    k[k==0]=1
    clustering_coefficient=2*triangles/k
   
    if glo==True:
        return np.mean(clustering_coefficient)
   
    return clustering_coefficient

def wei2unwei(mat):
    n=mat.shape[0]
    adjacency=np.zeros((n, n))
    adjacency[mat>0]=1
    return adjacency   
   
def triangle(weightedmat):
    n=weightedmat.shape[0]
    triangles=np.zeros(n)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                temp=weightedmat[i, j]*weightedmat[j, k]*weightedmat[k, i]
                triangles[i]+=pow(temp, 1/3)
 
    triangles/=2
    return triangles

def ERgraph(N, p):
    graph=np.zeros((N, N))
    i=0
    while i<N-1:
        j=i+1
        while j<N:
            if np.random.uniform(0, 1)<p:
                graph[i, j]=1
               
            j+=1
        i+=1
       
    graph=graph+graph.T
    return graph

n_nodes=80
p=0.5
cc_ergraph=[]
cpl_ergraph=[]

for i in range(100):
    temp=ERgraph(n_nodes, p)
    cc_ergraph.append(clustering_coefficient(temp))
    temp[temp==0]=inf
    cpl_ergraph.append(characteristic_path_length(temp))
   
plt.hist(cc_ergraph)
plt.xlabel('clustering coefficient')
plt.ylabel('frequency')
plt.title('cc_ergraph')
plt.show()
plt.hist(cpl_ergraph)
plt.xlabel('characteristic path length')
plt.ylabel('frequency')
plt.title('cpl_ergraph')
plt.show()
-----------------------------------------------

　ちょいと足りないくらいかな、という印象。
　次に、ノード数とER生成回数を変えてどうなるかを調べてみる。ノード数は50, 100個とし、それぞれに対してERグラフの生成回数を10, 30, 100, 200, 300, 500としたときの、Cと Lの値をヒストグラムで出してみる。また正規性の確認としてシャピロウィルク検定を行う。

-----------------------------------------------
N_NODES=[50, 100]
p=0.5
n_exams=np.array([10, 30, 100, 200, 300, 500])

for n_nodes in N_NODES:
    for n_exam in n_exams:
        cc_ergraph=[]
        cpl_ergraph=[]

        for i in range(n_exam):
            cpl_candidate=inf

            while cpl_candidate==inf:
                temp=ERgraph(n_nodes, p)
                cc_candidate=clustering_coefficient(temp)
                temp[temp==0]=inf
                cpl_candidate=characteristic_path_length(temp)

            cc_ergraph.append(cc_candidate)
            cpl_ergraph.append(cpl_candidate)

        fig=plt.figure(figsize=(16, 8))
        ax1=plt.subplot(121)
        ax2=plt.subplot(122)
       
        ax1.hist(cc_ergraph)
        ax1.set_xlabel('clustering coefficient')
        ax1.set_ylabel('frequency')
        ax1.set_title('cc_ergraph ('+str(n_nodes)+' nodes, '+str(n_exam)+' exams)')

        ax2.hist(cpl_ergraph)
        ax2.set_xlabel('characteristic path length')
        ax2.set_ylabel('frequency')
        ax2.set_title('cpl_ergraph ('+str(n_nodes)+' nodes, '+str(n_exam)+' exams)')
       
        plt.savefig(str(n_nodes)+'nodes_'+str(n_exam)+'exams.png')
       
        cc_temp=scipy.stats.shapiro(cc_ergraph)
        cpl_temp=scipy.stats.shapiro(cpl_ergraph)
        print('Shapiro-Wilk test (n_nodes='+str(n_nodes)+', n_exam='+str(n_exam)+')\ncc_ergraph: p='+str(cc_temp[1])+'\ncpl_ergraph: p='+str(cpl_temp[1])+'\n')
    
-----------------------------------------------
Shapiro-Wilk test (n_nodes=50, n_exam=10)
cc_ergraph: p=0.37558773159980774
cpl_ergraph: p=0.4100293517112732

Shapiro-Wilk test (n_nodes=50, n_exam=30)
cc_ergraph: p=0.14942386746406555
cpl_ergraph: p=0.8486078977584839

Shapiro-Wilk test (n_nodes=50, n_exam=100)
cc_ergraph: p=0.7921257615089417
cpl_ergraph: p=0.3289673328399658

Shapiro-Wilk test (n_nodes=50, n_exam=200)
cc_ergraph: p=0.039140429347753525
cpl_ergraph: p=0.4688810706138611

Shapiro-Wilk test (n_nodes=50, n_exam=300)
cc_ergraph: p=0.6537032723426819
cpl_ergraph: p=0.025576237589120865

Shapiro-Wilk test (n_nodes=50, n_exam=500)
cc_ergraph: p=0.22154365479946136
cpl_ergraph: p=0.8461586236953735

Shapiro-Wilk test (n_nodes=100, n_exam=10)
cc_ergraph: p=0.7797001600265503
cpl_ergraph: p=0.38541314005851746

Shapiro-Wilk test (n_nodes=100, n_exam=30)
cc_ergraph: p=0.6236131191253662
cpl_ergraph: p=0.6676943898200989

Shapiro-Wilk test (n_nodes=100, n_exam=100)
cc_ergraph: p=0.22231294214725494
cpl_ergraph: p=0.08100102841854095

Shapiro-Wilk test (n_nodes=100, n_exam=200)
cc_ergraph: p=0.09412982314825058
cpl_ergraph: p=0.5377574563026428

Shapiro-Wilk test (n_nodes=100, n_exam=300)
cc_ergraph: p=0.418567955493927
cpl_ergraph: p=0.4255199432373047

Shapiro-Wilk test (n_nodes=100, n_exam=500)
cc_ergraph: p=0.4211519658565521
cpl_ergraph: p=0.8973879814147949
-----------------------------------------------

　それぞれでCrand、Lrandがいくらになったのかを求めておくのを忘れてしまったのだが、分布がどうであれCrand、Lrand自体はn_examが小さくてもある程度の狭い範囲に収まっているようにみえる。なので最初にざっくりデータの傾向をみる時点ではそこまで大きな回数のERグラフを生成する必要はないようにも思う。2通りしかやってないので雰囲気でしか話せないが、ノード数と同じくらいでいいかな。厳密にデータ解析しようとしたら、最低でもノード数の2倍～4,5倍ってとこですか。
　その辺も含めて結局のところ、どの程度のブレ幅までなら許容できるかをその都度考えなきゃダメってことですかね。大げさな話、解析したい元のネットワークたちのCnetが0.3だったり0.7だったりとぶれてたら、Crandが0.45だろうが0.55だろうが解析はできそうですし。逆に0.49と0.51の違いを扱いたい場合には、かなりの回数が必要そう。

　それと、ここに載せてない試行の中で、n_examが大きいにも関わらずシャピロウィルク検定で正規性がないとされたことがままあった。そういうときでもヒストグラム的にはとんがりコーンになっていたので、今回の目的に対してシャピロウィルク検定はいまいちよくないのかもしれない。てっきり回数稼げば正規分布になるだろうと思い込んでいたので、これについては近日中に考えようと思う。

　また、もしかしてCrand、Lrandはノード数の影響を受けないかも？とも思い始めた。や、ノード数2つしか試してないのでとやかく言えないのだが、雰囲気で話しているのでお許し願いたい。上ではリンク率0.5で通してたので、こちらもいろいろ変えてみる必要がありそう。

　今後の課題
・ノード数と必要なERグラフの数の関係性
・上のリンク率による影響
・リンク率を変えたときのCrand、Lrandの変化をみる
・weighted networkへの応用(もともとweighted networkを扱いたかったのだが、weightedなランダムネットワークをどのように作るかを考えた結果、まずunweightedな場合についてちゃんと知ってからweightedな解析について検証しよう、というのが今回のモチベである)

トーナメントでチームメイトと出来るだけ当たらないようにしたい

　トーナメントの組み合わせ作成を完全に順位に従わせると、同じチームの人と早い段階でぶつかってしまうことがある。前回作成したプログラムの出力結果のトーナメント表を見てみると、こんなことになっている。

1回戦で同士討ち、勝者は2回戦でチームメイト(しかもシード！)と対戦

世界大会レベルなら仕方ない気もするが、一般的な試合でこういうことは避けるように組み合わせを考えたいので、そのようなものを考えてみる。
①最初にシードを分配(groups_only_ranker())
②参加者が最も多いチームの参加者数を超える最小の2^k個のブロックになるよう空のリストを追加(add_empty_groups())
③各ブロックにどのチームの人を入れるかを順に分配(dist_unranker())

tournament_distribution.py
--------------------------------------

#-*- coding:utf-8 -*-
import numpy as np
import random
def Nseed_group(Nseed, ranker_team, team_participant):
    #Input
    #Nseed: Number of seeds
    #ranker_team(vector): seed_team[i] means the team number of the (i+1)th ranker
    #team_participant: Number of participants of each teams (NumPy vector)
    team_ranker=cal_team_ranker(team_participant.shape[0], ranker_team)
   
    #Output
    #group list
   
    #get group list including only rankers
    group_list=groups_only_ranker(ranker_team)
   
    #add empty groups (unseed blocks) into group list
    group_list=add_empty_groups(group_list, np.max(team_participant))
   
    #unranker distribution
    team_unranker=team_participant-team_ranker    ##Number of unrankers of each teams
    group_list=dist_unranker(group_list, team_unranker, team_participant)
   
    return group_list
   
def cal_team_ranker(n_group, ranker_team):
    team_ranker=np.zeros(n_group)
   
    for i in range(n_group):
        team_ranker[i]=np.sum(ranker_team==(i+1))
       
    return team_ranker
def NumOfDigits_2(x):
    #Input
    #x: number
   
    #Output
    #k: the integer as "2^(k-1) < x <= 2^k"
   
    k=1
    while pow(2, k)<x:
        k+=1
       
    return k

def add_empty_groups(group_list, max_team_participant):
    #add empty groups (unseed blocks)
    #Input
    #group_list: group list with only seed blocks
    #max_team_participant: max number of one team participants (add empty blocks as number of blocks >= 2^k between two seed blocks)
   
    #Output
    #
    k1=pow(2, NumOfDigits_2(max_team_participant))
    k2=len(group_list)
   
    while k2<k1:
        temp=[]
        for i in range(np.int(k2/2)):
            temp.append(group_list[2*i])
            temp.append([])
            temp.append([])
            temp.append(group_list[2*i+1])
       
        group_list=temp
        k2=len(group_list)
       
    return group_list

def groups_only_ranker(ranker_team):
    #Input
    #ranker_team(vector): ranker_team[i] means the team number of the (i+1)th ranker
   
    #Output
    #groups(list):
   
    #get the order of seeds in tournament
    position=np.array([1, 2])
    p=1
    N=ranker_team.shape[0]
    while N>pow(2, p):
        i=0
        while i<pow(2, p-1):
            position=np.r_[position[:4*i+1], np.zeros(2), position[4*i+1:]]
            i+=1
        i=0
        while i<pow(2, p):
            if position[2*i]==0:
                position[2*i]=pow(2, p+1)+1-position[2*i+1]
            else:
                position[2*i+1]=pow(2, p+1)+1-position[2*i]
            i+=1   
        p+=1
   
    #make list of seed groups
    groups=[]
    for i in range(N):
        groups.append([ranker_team[np.int(position[i]-1)]])
       
    return groups

def dist_unranker(group_list, team_unranker, team_participant):
    for i in range(team_unranker.shape[0]):
        group_list=add_teamx(group_list, i+1, np.int(team_unranker[i]), np.int(team_participant[i]))
       
    return group_list

def add_teamx(group_list, x, added_n, group_n):
    digit=NumOfDigits_2(group_n)
    for i in range(added_n):
        group_list=add_teamx_one(group_list, pow(2, digit), x)
       
    return group_list

def add_teamx_one(group_list, group_num, x):
    num_group_teamx=np.zeros(group_num)
    num_group_allteam=np.zeros(group_num)
   
    num_partition=np.int(len(group_list)/group_num)
   
    for i in range(group_num):
        num_group_teamx[i]=np.sum(np.array([b for a in group_list[num_partition*i:num_partition*(i+1)] for b in a])==x)
        num_group_allteam[i]=len([b for a in group_list[num_partition*i:num_partition*(i+1)] for b in a])
       
    few_teamx_group_index=[]
    few_allteam_group_index=[]
   
    for i in range(group_num):
        if num_group_teamx[i]==np.min(num_group_teamx):
            few_teamx_group_index.append(i)
           
        if num_group_allteam[i]==np.min(num_group_allteam):
            few_allteam_group_index.append(i)
           
    index=choice_index(few_teamx_group_index, few_allteam_group_index)
    if num_partition==1:
        group_list[index].append(x)
    else:
        group_list[num_partition*index:num_partition*(index+1)]=add_teamx_one_partly(group_list[num_partition*index:num_partition*(index+1)], x)
    return group_list

def choice_index(few_teamx_group_index, few_allteam_group_index):
    commons=list(set(few_teamx_group_index) & set(few_allteam_group_index))
    if len(commons)==0:
        index=random.choice(few_teamx_group_index)
    elif len(commons)==1:
        index=commons[0]
    else:
        index=random.choice(commons)
       
    return index
   
def add_teamx_one_partly(group_list_partly, x):
    num_participants_in_partly_groups=np.zeros(len(group_list_partly))
    for i in range(num_participants_in_partly_groups.size):
        num_participants_in_partly_groups[i]=len(group_list_partly[i])
       
    few_allteam_partly_group_index=[]
    for i in range(num_participants_in_partly_groups.size):
        if num_participants_in_partly_groups[i]==np.min(num_participants_in_partly_groups):
            few_allteam_partly_group_index.append(i)
           
    index=few_allteam_partly_group_index[np.random.choice(len(few_allteam_partly_group_index))]
    group_list_partly[index].append(x)
    return group_list_partly

--------------------------------------
と関数を作成した。

動作検証で次のようにする。
ranker_team: 1位から順にランカーのチームIDを並べたNumpy配列
team_participant: チームID順に各チームの参加者数を並べたNumpy配列

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

ranker_team=np.array([1, 4, 7, 3, 2, 6, 7, 12, 3, 2, 18, 15, 21, 4, 1, 3])
team_participant=np.array([12, 18, 10, 8, 16, 13, 12, 14, 7, 5, 6, 9, 7, 11, 5, 4, 8, 8, 9, 10, 13, 12])
temp=Nseed_group(16, ranker_team, team_participant)

for i in temp:
    print(i)

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

[1, 2, 6, 8, 14, 20]
[2, 4, 5, 11, 13, 19, 22]
[1, 6, 7, 9, 17, 19]
[3, 5, 8, 10, 14, 18, 21]
[3, 2, 6, 9, 15, 20, 22]
[1, 4, 5, 7, 14, 17, 21]
[1, 2, 6, 11, 13, 18]
[12, 5, 7, 10, 16, 20, 21]
[2, 3, 5, 12, 14, 17, 22]
[1, 4, 7, 8, 16, 18, 20]
[2, 5, 6, 8, 13, 20, 21]
[15, 2, 7, 9, 14, 19, 22]
[21, 3, 7, 12, 17, 20]
[2, 4, 5, 8, 13, 19, 22]
[2, 6, 7, 10, 12, 18]
[3, 5, 8, 9, 15, 19, 21]
[7, 2, 8, 10, 14, 20, 22]
[2, 5, 6, 11, 13, 19, 21]
[1, 2, 6, 9, 15, 18, 21]
[4, 3, 5, 8, 14, 17, 22]
[18, 3, 6, 12, 14, 17, 21]
[1, 4, 5, 8, 16, 19, 22]
[1, 2, 7, 11, 14, 20, 22]
[6, 2, 5, 8, 13, 19]
[7, 2, 8, 10, 12, 20, 22]
[1, 3, 5, 11, 14, 16, 21]
[1, 3, 5, 8, 12, 17, 21]
[2, 4, 6, 9, 13, 18]
[1, 3, 6, 9, 14, 17, 21]
[2, 5, 7, 8, 12, 18, 22]
[1, 5, 6, 8, 12, 19, 22]
[4, 2, 7, 11, 15, 20, 21]

--------------------------------------
　乱数を使うので生成するたびに異なる結果が返ってくるので、これは一例。
　おおむねうまくいっているように見えるが、それでもうまく分配できていない。1行目のブロックを勝ち進んだ人は2行目のブロックを勝ち進んできた人と対戦するが、ここでチームID2の同士討ちが起きる可能性がある。その一方3, 4行目にはチームID2が含まれていない。このことは1, 2行目のどちらかのチームID2が3, 4行目のどちらかにいれば避けられた同士討ちである。また他との兼ね合いの関係でどうしても出来てしまう同士討ちならともかく、少なくとも今の例でいえば4行目の3と交換する分には、他に同士討ちを生じるわけでもない。多分探せば他にもいっぱいありそう。

　頭で考えているアルゴリズムだとそういうことはないはずなので、うーんと頭を抱えている。その一方で、人数がおおむねそろっているのが逆に予想外だった。同士討ちが絶対に最遠になるようにしたはずなので、各ブロックの人数が2人以上離れることもあると思ったが、実際には6か7人で大体そろっている。

　うーん。わからん。

https://github.com/nkknj/magimenalmirai/blob/master/20180828/tournament_distribution.py

トーナメント表の作成

　前回の続きとして、openpyxlでトーナメント表を作成した。とりあえず参加者が一列に並んでいる状態のもの。

　プログラムの途中までは、一昨日のものと全く一緒。その後ろでopenpyxlで作業をしている。手順として、

(1)左に必要な選手情報を並べる。

(2)横に線を引く

(3)上から順次2回戦分の線を引いていく。(条件分岐: シード横の場合1回戦分の線も引く)

(4)線を引くのと同時に順次試合番号の記入

(5)3回戦以降は各位置に対応するインデックスを保持して、インデックス2個ずつで順次線を引くと同時に試合番号の記入

list2tournament.py

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

import sys
import numpy as np
import pandas as pd
import openpyxl
from openpyxl.styles import Alignment, Border, Side

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)

#tournament pairs considering rank
N=rank.shape[0]

position=np.array([1, 4, 3, 2])
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

wb=openpyxl.Workbook()
ws=wb.active
ws.title='tournament'

#ヘッダー部を2行ごとに結合
#前6列にID, 選手姓, 選手名, '(', チーム名, ')'
n_header=6
i=1
while i<=position.shape[0]:
    #i行目の処理
   
    #i行目j列の結合と設定
    j=1
    while j<=n_header:
        ws.merge_cells(start_row=2*i-1, start_column=j, end_row=2*i, end_column=j)
        ws.cell(row=2*i-1, column=j).alignment=Alignment(
            wrap_text=False,
            horizontal='center',
            vertical='center',
        )
        j+=1

    #ここで列幅の自動調整をさせたいができていない
    #while j<=n_header:
    #    ws.col_dimensions[j].alignment=Alignment(
    #        ShrinkToFit=True
    #    )
    #    j+=1
   
    #ヘッダー中身書き込み
    ws.cell(row=2*i-1, column=1, value=i)
    ws.cell(row=2*i-1, column=4, value='(')
    ws.cell(row=2*i-1, column=6, value=')')
   
    if position[i-1]==0:
        ws.cell(row=2*i-1, column=2, value='bye')
    else:
        ws.cell(row=2*i-1, column=2, value=rank['選手姓'][position[i-1]])
        ws.cell(row=2*i-1, column=3, value=rank['選手名'][position[i-1]])
        ws.cell(row=2*i-1, column=5, value=rank['チーム名'][position[i-1]])
    i+=1

#1, 2回戦分
n_round1=1
n_round2=1
list_index=[]
n_seed=pow(2, p2)
i=1
while i<position.shape[0]:
    temp=position[i-1:i+2]
    if np.min(temp)==0:
        temp[np.argmin(temp)]=np.max(temp)
       
    if np.min(temp)<=n_seed:
        #連続する3人の中にシードが含まれる場合
        if np.argmin(temp)==0:
            #若番側がシードの場合
            ws.cell(row=2*i, column=n_header+1).border=Border(
                outline=True,
                top=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*i, column=n_header+2).border=Border(
                outline=True,
                top=Side(style='medium', color='FF000000'),
                right=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*(i+1), column=n_header+1).border=Border(
                outline=True,
                top=Side(style='medium', color='FF000000'),
                right=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*(i+1)+1, column=n_header+1).border=Border(
                outline=True,
                bottom=Side(style='medium', color='FF000000'),
                right=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*(i+1), column=n_header+2).border=Border(
                outline=True,
                bottom=Side(style='medium', color='FF000000'),
                right=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*(i+1)-1, column=n_header+2).border=Border(
                outline=True,
                right=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*i, column=n_header+3).border=Border(
                outline=True,
                bottom=Side(style='medium', color='FF000000'),
            )
            ws.cell(row=2*i, column=n_header+2, value='2-'+str(n_round2))
            ws.cell(row=2*(i+1), column=n_header+1, value='1-'+str(n_round1))
            ws.cell(row=2*i, column=n_header+2).alignment=Alignment(
                wrap_text=False,
                horizontal='right',
                vertical='center',
            )
            ws.cell(row=2*(i+1), column=n_header+1).alignment=Alignment(
                wrap_text=False,
                horizontal='right',
                vertical='center',
            )
            n_round1+=1
            n_round2+=1
            list_index.append(2*i)
        else:
            #若番側は1回戦スタートの場合
            ws.cell(row=2*i, column=n_header+1).border=Border(
                outline=True,
                top=Side(style='medium', color='FF000000'),
                right=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*i+1, column=n_header+1).border=Border(
                outline=True,
                bottom=Side(style='medium', color='FF000000'),
                right=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*i+1, column=n_header+2).border=Border(
                outline=True,
                top=Side(style='medium', color='FF000000'),
                right=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*(i+1), column=n_header+2).border=Border(
                outline=True,
                right=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*i+3, column=n_header+1).border=Border(
                outline=True,
                bottom=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*i+3, column=n_header+2).border=Border(
                outline=True,
                bottom=Side(style='medium', color='FF000000'),
                right=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*(i+1), column=n_header+3).border=Border(
                outline=True,
                bottom=Side(style='medium', color='FF000000')
            )
            ws.cell(row=2*i, column=n_header+1, value='1-'+str(n_round1))
            ws.cell(row=2*(i+1), column=n_header+2, value='2-'+str(n_round2))
            ws.cell(row=2*i, column=n_header+1).alignment=Alignment(
                wrap_text=False,
                horizontal='right',
                vertical='center',
            )
            ws.cell(row=2*(i+1), column=n_header+2).alignment=Alignment(
                wrap_text=False,
                horizontal='right',
                vertical='center',
            )
            n_round1+=1
            n_round2+=1
            list_index.append(2*(i+1))
        i+=3
    else:
        #連続する3人にシードがいない場合
        ws.cell(row=2*i, column=n_header+1).border=Border(
            outline=True,
            top=Side(style='medium', color='FF000000')
        )
        ws.cell(row=2*i+1, column=n_header+1).border=Border(
            outline=True,
            bottom=Side(style='medium', color='FF000000')
        )
        ws.cell(row=2*i, column=n_header+2).border=Border(
            outline=True,
            top=Side(style='medium', color='FF000000'),
            right=Side(style='medium', color='FF000000')
        )
        ws.cell(row=2*i+1, column=n_header+2).border=Border(
            outline=True,
            bottom=Side(style='medium', color='FF000000'),
            right=Side(style='medium', color='FF000000')
        )
        ws.cell(row=2*i, column=n_header+3).border=Border(
            outline=True,
            bottom=Side(style='medium', color='FF000000')
        )
        ws.cell(row=2*i, column=n_header+2, value='2-'+str(n_round2))
        ws.cell(row=2*i, column=n_header+2).alignment=Alignment(
            wrap_text=False,
            horizontal='right',
            vertical='center',
        )
        n_round2+=1
        list_index.append(2*i)
        i+=2

#3回戦以降
r=3 #階層数
while len(list_index)>1:
    temp=[] #次のlist_index
    n_roundr=1
    i=0
    while i<len(list_index):
        x=list_index[i]+1
        ws.cell(row=x, column=n_header+r).border=Border(
            outline=True,
            top=Side('medium', color='FF000000'),
            right=Side(style='medium', color='FF000000')
        )
        x+=1
        while x<list_index[i+1]:
            ws.cell(row=x, column=n_header+r).border=Border(
                outline=True,
                right=Side(style='medium', color='FF000000')
            )
            x+=1
        ws.cell(row=x, column=n_header+r).border=Border(
            outline=True,
            bottom=Side('medium', color='FF000000'),
            right=Side(style='medium', color='FF000000')
        )
       
        ws.cell(row=(list_index[i]+list_index[i+1])/2, column=n_header+r, value=str(r)+'-'+str(n_roundr))
        ws.cell(row=(list_index[i]+list_index[i+1])/2, column=n_header+r).alignment=Alignment(
            horizontal='right',
            vertical='center'
        )
        n_roundr+=1
        temp.append((list_index[i]+list_index[i+1])/2)
        i+=2
       
    list_index=temp
    r+=1

ws.cell(row=list_index[0], column=n_header+r).border=Border(
    outline=True,
    bottom=Side('medium', color='FF000000')
)
wb.save('tournament.xlsx')

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

　これで

　　python3 list2tournament.py sample.xlsx

でtournament.xlsxが出力される。(←これスマホからみたらとんでもないことになってて笑った)

　シート分けやら左右に分けたりする場合、その時々に合わせてシートを何枚にするかなどを事前に決めてからであれば可能そう。

https://github.com/nkknj/magimenalmirai/tree/master/20180817

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

　必要になったときにサッと用意できるように、もとい暇つぶしとして、トーナメントの組み合わせを作成するプログラムを考えてみる。
　(作成したスクリプトなどを置く場所を作った。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があるので、これは上記と同じ方法をとっていそうである。なのでまぁ、この辺はローカルルールなんかね。

研究発表振り返りと今後

　今回研究発表の準備をするにあたって、立てていた目標を振り返る。
・発表前週までには完成させ、きたる卒試への準備を始める
　結局直前の直前までやってた。研究内容を説明するのに必要な要素を網羅しつつ、論理が一直線な話を作るのがとても大変だった。単語の厳密性を維持しつつ簡単にするのがとても難しい…聴衆がその分野のヒトの場合とはまた違う難しさよね。

・各スライドのタイトルが断定の形で書かれているやつを作る
　単語じゃなくて「～である」って書かれてるタイプのスライドでやってみたかった。果たされた。

・聴衆のレベルを意識したプレゼンを作る
　質問が出てきてくれたので、理解してくれた人が一定数いるということで及第点。ただ、うれしい質問をしてくれた人は独学でそういうことやろうとしてた人だったってことが後から判明したんすけどね。

・落ち着いた低い声でしゃべる
　いままでのコアタイムやらの発表でも必ず毎度高音早口トークになっていたので今度こそはと思っていたが、結局いつも通りどころかいつも以上に高音早口トークになってしまった。準備不足が原因。

・炎上しない
　深い内容については若干はぐらかした感じがあるが炎上には至らず。他には、聞かれた内容がちょうどラボとは関係なくテキトーに読み漁ってた内容だったりしたので、半年間を肯定された気分になった。再現性の話についてはキニシテハイケナイ。

　ひとまずひと段落ついたし、頑張ったところでそれをまとめて成果として出すのはだいぶ先になってしまうだろうし、これをもって研究活動は終えても問題ない。問題ないのだが、暇があれば考えてしまう。まあこれくらいはいいか。
　今日からは完全に卒試対策モードや！と決めていたものの、講義5コマも聞いたら疲れ果ててしまい、その後ゼミ室ではネットサーフィンして終わってしまった。一日くらいはゆっくりしても仕方ないか、と今日のことは正当化しておいて、明日からはちゃんと卒試対策に力を入れようと思う。

2018上半期雑考

　ラボでの半年間の生活が終わった。元はこの期間は数学の勉強に力を入れて、研究はテキトーにやってテキトーにまとめればいいや程度に思っていた。しかし思ったより研究の方に力を注ぐ必要があったので、思っていたほど数学の学習は進められなかった。またこの半年間でさらにいろんな分野の話を聞いて、さらに高度な数学の必要性の存在を思い知るなどした。今後当分数学には触れられないだろうから、また次に学習できる時期が来た頃にはすっかり忘れてしまっていそうで、とても悲しい。
　その傍らツイッターを見ていると、UTの数学強い人で同じような興味を持っている人が「数学がわからない」と言っているのをたびたび見かける。この人でもわからない数学を俺が理解するには一体どれだけの時間が必要になるのかと思う。ともすれば一生を費やしても理解できないのではないかと思う。これに人生をかけるのは凡人がするようなことではない。あくまで娯楽として長期間続けて、もしそれが理解できたり、結果人生が豊かになったらラッキーくらいのものだろう。
　そう考えると、今後俺がその分野に進むのはナンセンスな気がする。今回のようにラボのテーマから逸脱すると、指導教官だってゼロから指導する余力はないし、独学ではどうにも自分の思考が正しいかどうか自信がない。凡人は凡人らしく、ラボのテーマに沿って上司の指導を受けながら学習と成果を効率よく生産するべきなのではないか。または、どうしてもやりたい分野があるなら、その分野の最先端のラボで研究するかである。しかしその場合には臨床の道からは外れてることを覚悟しなければならないし、その場合には年齢的ビハインドを持つことになる。天才様なら話は別だが、凡人は凡人なりの生き方をしなければならない。医師免許を取るにはどんな天才様でも6年間かかるわけで、専門医となればさらに数年かかる。大学入学からの5.5年間で、特に前半ではもっと勉強して強くなることはできたかもしれないが、少なくともこの5.5年間は医師免許を得るために必要な5.5年間として機能するのであれば、その持て余した時間もただ無駄にしたわけではない。
　さらには、もしその分野に進まないとして、それで学ぶことをやめる程度なら、やはりその分野には進むべきではないのだろう。もしやりたければ必要なくてもやるのだから、本業はそれ以外でやれることをやるスタイルでいい。
　それにしてもこの分野、同じ臓器見てるのに本当に研究者によって全然見方が違う。かなり離れた2領域を掛け持ちしているようなものなので、とても強くその印象を受ける。このどちらが正しいというわけではなく、どっちも必要なんだろう。とすると、研究者の多様性という意味で、本業とはかけ離れた自分のやりたい勉強をやるというのは、凡人の凡人として出来ることなのではないかと思う。さらにはやりたい勉強に限らず、音楽も読書もスポーツも、友達も人間関係も、あらゆる要素がこの多様性に関わる。
　つまり何をしてもそれは無駄にはならない。もちろんこれはくいっぱぐれることはないという前提での話なので、もし将来医師過剰にでもなったら話は変わってくるが、親の生き方を聞いていると、その時はその時でどうにでもなるという感じがする。今苦しんで努力して学んだことも、ラクに楽しくやったことも、どちらも等しく武器にも無駄にもなりうる。ならラクに楽しく生きた方がいいな。苦しくても結果何かを明らかにするのは幸せ、みたいな生き方もあるとは思うが、幸せになる方法は少なくとも俺にはそれだけではない。
　上で書いたように、やらなきゃいけない数学やらなんやらがあまりに多すぎて、これから国家試験対策に向かうのがあまりにばかばかしく思っていたが、これをもってひとまずリセットして国家試験対策を開始しようという気にもなれそうだ。この半年間、脳機能をフル稼働してノロノロとしか読み進まないものをずっと読んできた。元は自由に使える半年間だったのに、いざその半年間に入ると「大量の知識を半年で詰め込まなければならない」と焦っていた気がする。もっと肩の力抜いてもよかったな。数学は2, 3月にやろう。今日はなんとなく小説を買ってきたので、土日はこれ読んで脳内洗浄といこう。
　そして国試対策へ。

　この記事、後から見てこっぱずかしくなるんかなー。

3939日以後の記念日を探す

　初音ミク生誕3939日目！最近はラボでの進捗報告に「ダイナ『ミク』ス」という言葉を入れることくらいしか初音ミク活動をできていない。(ん？) せっかくの3939th dayなので、何かしようと思うが時間的にも何も出来なさそう。次の3939th day的な初音ミクの記念日的サムシングないかな～と思いを馳せたので、それをまとめることでこの3939th dayの活動とする。

　ルールは2つ。
　　・どんなこじつけでもOK
　　・2100年まで

ミク(39)
39=2028/2/26
39=2028/4/13
西暦下2桁: 2039年
平成39年: 2027年
新元号39年: 2057年
39歳の誕生日: 2046/8/31
3^9日(=19683日): 2061/7/20

ミクさん(393)
393ヵ月: 2040/5/31

ミクミク(3939)
3939日: 2018/6/12
3939週間(=27573日): 2083/2/25
39*39週間(=10647日): 2036/10/23

ミクミクミク(393939)
393939時間(≒16414.1日): 2052/8/7

ミクミクミクミク(39393939)
39393939分(≒27356.9日): 2082/7/23, 24 ※生誕時刻の定義による

初音ミクの循環(1/39の循環節は256410)
256410時間(=10683.75): 2036/11/28, 29 ※生誕時刻の定義による

野菜(831)
831週間: 2023/8/3
831ヵ月: 2076/11/30

よろミク(4639)
4639日: 2020/5/12

ミクの素数(39番目の素数)(167)
167ヵ月: 2021/7/31

ミクさんの素数(393番目の素数)(2699)
2699週間: 2059/5/22

数字ありきではない記念日
2023/8/31: 実年齢が設定に追いつく

時系列順にすると
2018/6/12: 3939日
2020/5/12: 4639日
2021/7/31: 39番目の素数167ヵ月
2023/8/3: 831週間
2023/8/31: 実年齢が設定に追いつく
2028/2/26=39
2028/4/13=39
2036/10/23: 39*39週間
2036/11/28: 1/39の循環節256410時間
2039年: 下2桁
2040/5/31: 393ヵ月
2046/8/31: 39歳の誕生日
2052/8/7: 393939時間
2057年: 新元号39年
2059/5/22: 393番目の素数2699週間
2061/7/20: 3^9日
2076/11/30: 831ヵ月
2083/2/25: 3939週間
2082/7/23: 39393939分

　その他候補となった数にはミクミクな素数(3939番目の素数)(37181)、ミクのフィボナッチ数(39番目のフィボナッチ数)(63245986)がありましたが、2100年までに収まる記念日を定められませんでした。
　他にもあるぞ！やこれ間違ってるぞ！などありましたら、コメ欄またはtwitterにて@8_deg_50までお教えいただければと思います。
　さて、何の創作も間に合わなかったので、今日を開始日として何かをしよう。なにをするかなぁ。

　それにしても記念日は思っていたよりだいぶ少なかった。記念日に依存して創作をするなら、自分で記念日を作っていく強い意志を持つのが手っ取り早いのなぁ。まー記念日がたくさんあっても珍しみがなくなったら意味ないもんな。
　珍しみのない記念日の例として、年/(月*日)の余りが39になる日を羅列しておく。

2019/2/22
2019/3/15, 20, 22
2019/3/22, 30
2019/4/11, 15
2019/5/9, 11, 12, 18, 22
2019/6/10, 11, 15, 22, 30
2019/9/5, 10, 11, 20, 22
2019/10/6, 9, 11, 18, 22
2019/11/4, 5, 6, 9, 10, 12, 15, 18, 20, 30
2019/12/5, 11, 15
2023/4/16
2023/8/8, 31
2028/3/17
2028/9/13, 17
2034/3/19
2034/5/19, 21
2034/7/15, 19
2037/2/27
2037/3/18
2037/6/9
2037/9/6
2039/2/20, 25
2039/4/10, 20, 25
2039/5/8, 10, 16, 20, 25
2039/8/5, 10, 25
2039/10/4, 5, 8, 10, 20, 25
2040/3/23, 29
2041/7/11, 13, 22, 26
2041/11/7, 13, 14, 26
2048/7/7
2054/5/13, 31
2055/2/21, 24, 28
2055/3/14, 16, 21, 24, 28
2055/4/12, 14, 18, 21, 24, 28
2055/6/7, 8, 12, 14, 16, 21, 24, 28
2055/7/6, 8, 9, 12, 16, 18, 24
2055/8/6, 7, 9, 12, 14, 18, 21, 28
2055/9/7, 8, 14, 16, 28
2055/12/4, 6, 7, 8, 12, 14, 21, 24, 28
2062/7/17
2063/2/22, 23
2063/4/11, 22, 23
2063/8/11, 23
2063/11/4, 8, 23
2064/3/15, 25, 27
2064/5/9, 15, 27
2064/9/5, 9, 15, 25
2067/2/26
2067/3/26
2067/4/13
2067/6/13, 26
2067/12/13
2069/2/29
2069/5/14, 29
2069/7/10, 29
2069/10/7, 29
2074/5/11
2074/11/5
2079/2/20
2079/3/17, 20
2079/4/10, 15, 17, 30
2079/5/8, 12, 17, 24
2079/6/10, 17, 20
2079/8/5, 15, 17
2079/10/4, 6, 12, 17
2079/12/5, 10, 17
2085/3/22, 31
2085/6/11
2085/11/6
2087/4/16
2087/8/8, 16
2089/2/25
2089/5/10
2089/10/5
2091/2/27
2091/3/18, 19
2091/4/19, 27
2091/6/9, 18, 19
2091/9/6, 12, 19
2091/12/9, 19
2096/11/11, 17
2097/2/21
2097/3/14
2097/6/7
2097/7/6, 7, 14, 21