総当たり戦アルゴリズムをPythonで書いてみる(1)

著者はボウリングにおけるリーグ戦に参加経験があり、毎週1名との対戦となっていて、どのような仕組みで全員と対戦しているのかに興味を持った。

トーナメント戦での総対戦数は、参加人数をnとすると(n-1)戦。総当たり戦での対戦数はn(n-1)/2戦、という知識まではあった。

「総当たり戦」で検索してみると、以下のような、Kirkmanによる、円を使用した試合の組み合わせを決めるアルゴリズムがあるようだ。　

意外と簡単!1vs1の総当りリーグ戦のスケジュール - Korokorotuneのブログ

図形をそのまま使うのは難しいので、プログラム化しやすい図などないものかと、別の形式を見つけた。

リーグ戦形式(総当たり)の試合日程を組む方法

こちらの方が、初期値が実際に即したものになっているので、参考にした。

このようなPythonでコードを書いてみた。

print("*** Round Robin ***")

members = int(input("number of member :"))
print(members)

n = members
w = 1
x = [i for i in range(1, n, 2)]
y = [i for i in range(2, n+1, 2)]

print(x)
print(y)

print("Week {}".format(w))
for i in range(len(x)):
   print("{}-{}".format(x[i], y[i]))

for w in range(2, n):
   print("Week {}".format(w))

   x.append(y[len(x)-1])
   y.insert(0, x[1])
   x.pop(1)
   y.pop()

   print(x)
   print(y)

   for i in range(len(x)):
       print("{}-{}".format(x[i], y[i]))

改良点はあるかもしれぬが、例として10名での出力はできているので、以下に示す。

*** Round Robin ***
number of member :10
10
[1, 3, 5, 7, 9]
[2, 4, 6, 8, 10]
Week 1
1-2
3-4
5-6
7-8
9-10
Week 2
[1, 5, 7, 9, 10]
[3, 2, 4, 6, 8]
1-3
5-2
7-4
9-6
10-8
Week 3
[1, 7, 9, 10, 8]
[5, 3, 2, 4, 6]
1-5
7-3
9-2
10-4
8-6
Week 4
[1, 9, 10, 8, 6]
[7, 5, 3, 2, 4]
1-7
9-5
10-3
8-2
6-4
Week 5
[1, 10, 8, 6, 4]
[9, 7, 5, 3, 2]
1-9
10-7
8-5
6-3
4-2
Week 6
[1, 8, 6, 4, 2]
[10, 9, 7, 5, 3]
1-10
8-9
6-7
4-5
2-3
Week 7
[1, 6, 4, 2, 3]
[8, 10, 9, 7, 5]
1-8
6-10
4-9
2-7
3-5
Week 8
[1, 4, 2, 3, 5]
[6, 8, 10, 9, 7]
1-6
4-8
2-10
3-9
5-7
Week 9
[1, 2, 3, 5, 7]
[4, 6, 8, 10, 9]
1-4
2-6
3-8
5-10
7-9
​

これですべての組み合わせが表示できている。表示順序は、先頭が常に1となっているので、適宜、並べ替えたい。

次回に続く