15 人の女生徒が毎日 3 人ずつ 5 組に分かれて散歩をするとき、1 週間 (7 日) のうちに、どの女生徒も他のすべての女生徒と 1 回ずつ同じ組になるような組み合わせを作ってください。
出典 : 大村平 (著), 『数理パズルの話』, 日科技連出版社, 1998
「カークマンの 15 人の女生徒」を解くプログラムを Python で作ってください。
「カークマンの 15 人の女生徒」の解法プログラムは、集合の分割とベル数 の問題 3 で作成した関数 group_partition() を改造することで簡単に作成することができます。次のリストを見てください。
リスト : 女生徒の管理
# チェック用 (0 はダミー)
check_table = [[] for _ in range(16)]
# 生徒 y と散歩していないことを確認する
def check_student(xs, y):
for x in xs:
if y in check_table[x]: return False
return True
# 女生徒の追加
def add_student(xs, y):
for x in xs:
check_table[x].append(y)
check_table[y].append(x)
# 女生徒の削除
def del_student(xs, y):
for x in xs:
check_table[x].pop()
check_table[y].pop()
15 人の女生徒を 1 から 15 までの整数で表します。大域変数 check_table は、いっしょに散歩した人を格納するリストです。0 番目はダミーです。たとえば、[1, 2, 3] というグループを作った場合、check_table の 1 番目は [2, 3] に、2 番目は [1, 3] に、3 番目は [2, 3] になります。この check_table を使って、同じ女生徒と 2 回以上散歩しないようにグループ分けを行います。
関数 check_student() はグループ xs に y を追加するとき、既に散歩した女生徒がいるかチェックします。check_table[x] からリストを取り出し、それに y が含まれていれば、y は既に x と散歩をしています。この場合は False を返します。y が xs の女生徒達とまだ散歩していない場合は True を返します。
関数 add_student() は check_table にグループ xs と y の関係を追加します。xs の要素を x とすると、check_table の x 番目のリストに y を、y 番目のリストに x を追加するだけです。関数 del_student() は xs と y の関係を削除します。xs の要素を x とすると、check_table の x 番目の末尾要素と、y 番目の末尾要素を削除します。
次は問題を解く関数 kirkman() を作ります。
リスト : カークマンの 15 人の女生徒
def kirkman_sub(j, a, b):
if j == 16:
b.append(a)
if len(b) == 7:
print_answer(b)
return True
if kirkman_sub(2, [[1]], b):
return True
b.pop()
else:
for i in range(len(a)):
if len(a[i]) < 3 and check_student(a[i], j):
add_student(a[i], j)
a[i].append(j)
if kirkman_sub(j + 1, a, b):
return True
a[i].pop()
del_student(a[i], j)
if len(a) < 5:
a.append([j])
if kirkman_sub(j + 1, a, b):
return True
a.pop()
return False
def kirkman():
kirkman_sub(2, [[1]], [])
実際の処理は関数 kirkman_sub() で行います。引数 j が女生徒を表す整数、a が作成中のグループ分けを格納するリスト、b が完成したグループ分けを格納するリストです。b の長さが 7 になれば解を見つけたことになります。
プログラムでは、j が 16 になったら a がひとつ完成したので、a を b に追加します。そして、len(b) が 7 になったら解をひとつ見つけたので、関数 print_answer() で b を表示して探索を終了します。そうでない場合は、kirkman_sub() を再帰呼び出しして次の日のグループ分けを作成します。
グループ分けの処理は group_partition() とほぼ同じですが、check_student() でチェックを行い、add_student() で check_table を更新してから、kirkman_sub() を再帰呼び出しします。再帰呼び出しから戻ってきたら、del_person() で check_table を元に戻します。
あとは特に難しいところはないと思います。詳細は プログラムリスト をお読みください。
それでは実行結果を示します。
>>>> s = time.time(); kirkman(); time.time() - s [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12], [13, 14, 15]] [[1, 4, 7], [2, 5, 10], [3, 6, 13], [8, 11, 14], [9, 12, 15]] [[1, 5, 14], [2, 4, 15], [3, 8, 12], [6, 9, 11], [7, 10, 13]] [[1, 9, 13], [2, 7, 12], [3, 4, 11], [5, 8, 15], [6, 10, 14]] [[1, 8, 10], [2, 11, 13], [3, 5, 9], [4, 12, 14], [6, 7, 15]] [[1, 6, 12], [2, 9, 14], [3, 10, 15], [4, 8, 13], [5, 7, 11]] [[1, 11, 15], [2, 6, 8], [3, 7, 14], [4, 9, 10], [5, 12, 13]] 14.838966131210327 実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
実行時間は PyPy3 で約 15 秒でした。興味のある方はプログラムの高速化に挑戦してみてください。
#
# kirkman.py : カークマンの 15 人の女生徒
#
# Copyright (C) 2022 Makoto Hiroi
#
import time
# チェック用 (0 はダミー)
check_table = [[] for _ in range(16)]
def check_student(xs, y):
for x in xs:
if y in check_table[x]: return False
return True
def add_student(xs, y):
for x in xs:
check_table[x].append(y)
check_table[y].append(x)
def del_student(xs, y):
for x in xs:
check_table[x].pop()
check_table[y].pop()
def print_answer(xs):
for x in xs: print(x)
def kirkman_sub(j, a, b):
if j == 16:
b.append(a)
if len(b) == 7:
print_answer(b)
return True
if kirkman_sub(2, [[1]], b):
return True
b.pop()
else:
for i in range(len(a)):
if len(a[i]) < 3 and check_student(a[i], j):
add_student(a[i], j)
a[i].append(j)
if kirkman_sub(j + 1, a, b):
return True
a[i].pop()
del_student(a[i], j)
if len(a) < 5:
a.append([j])
if kirkman_sub(j + 1, a, b):
return True
a.pop()
return False
def kirkman():
kirkman_sub(2, [[1]], [])