 |
| 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
