はじめに
ワークショップなどでサブグループを何度か作成する際、各回ごとのメンバーができるだけ異なるようにチーム分けをしたいことがあります。このようなチーム分けを計算するプログラムを作成しました。
実装は以下で公開しています。
今回は以下のような問題を考えます。
- 総人数nとチーム数kが与えられる
- 各チームの人数はn//kまたはn//k+1とする
- チーム分けを繰り返し、全員が自分以外のメンバーと1回以上同じチームになった時点で終了する
- breakしたときに、突出して多く同じチームになったペアが発生しないようにする、かつ、終了までの回数をできるだけ減らす
- nは15以下とする
方針
この設定はよくある課題に思われるので、標準的な解法があると期待しましたが、ドンピシャな解法は調べた範囲では見つかりませんでした。類似の問題はいくつか見つかりました。
nが大きくなると組み合わせが膨大になるため、意外と難しいようで、より一般的な問題として解くことを想定して、やきなまし法を使った実装などが見つかりました。
ただ、筆者がやきなまし法に慣れていないことと、具体的な利用シーンを想定したときに今回はnが少ないため、総当たりで解くことにしました。
総当たりであれば、以下のようなシンプルな考え方で解けそうです。
- n人をkチームに分ける全ての組み合わせを得る
- history_matrix（n人の各ペアが同じチームになった回数のマトリクス）をコストとして、与えられたhistory_matrixのもとでコストを最小にする1回分のチーム分けを求める
- 得られたチームでhistory_matrixを更新する
- 上記をhistory_matrixの値がすべて1以上になるまで繰り返す
総当たりが通用するnのサイズについては、以下によると、n=10のときに、チームの分け方が10万オーダーくらいらしいので、その前後くらいまでならなんとかなるのではないかという感じです。手元のPCではn=15までが限界でした。
また、このやり方で常に厳密解が求められるのかは不明ですが、概ねうまくいくのではないかと思います。
実装
方針に基づいて、Pythonでプログラムを作成しました。
工夫点として、チーム分けの際のコスト計算で、同じチームになった回数の二乗の合計を使用しています。これにより、特定のペアが連続して同じチームになることを防ぐことを目的としています。
import tqdm
from itertools import combinations
def generate_team_combinations(n, k):
# 各チームの最小人数
min_team_size = n // k
# 余りの人数
remainder = n % k
# チームのサイズを決定
team_sizes = [min_team_size + 1 if i < remainder else min_team_size for i in range(k)]
# 全ての組み合わせを生成
def generate_combinations(people, sizes):
if not sizes:
return [[]]
current_size = sizes[0]
rest_sizes = sizes[1:]
combinations_list = []
for team in combinations(people, current_size):
remaining_people = [p for p in people if p not in team]
for rest in generate_combinations(remaining_people, rest_sizes):
combinations_list.append([list(team)] + rest)
return combinations_list
# 人のリストを作成
people = list(range(n))
return generate_combinations(people, team_sizes)
def find_min_cost_combination(team_combinations, history_matrix):
min_cost = float('inf')
best_combination = None
for combination in team_combinations:
cost = 0
for team in combination:
for i in range(len(team)):
for j in range(i + 1, len(team)):
cost += history_matrix[team[i]][team[j]]
if cost < min_cost:
min_cost = cost
best_combination = combination
return best_combination
def update_history_matrix(history_matrix, teams):
updated_history_matrix = [row[:] for row in history_matrix]
for team in teams:
for i in range(len(team)):
for j in range(i + 1, len(team)):
updated_history_matrix[team[i]][team[j]] += 1
updated_history_matrix[team[j]][team[i]] += 1
return updated_history_matrix
def generate_teams(n, k, max_iter=20):
# team_combinationsをすべて求める
team_combinations = generate_team_combinations(n, k)
# history_matrixの初期値（すべて0）を生成
history_matrix = [[0] * n for _ in range(n)]
# 対角成分は1にする
for i in range(n):
history_matrix[i][i] = 1
# 結果のリスト
result = []
for _ in tqdm.tqdm(range(max_iter)): #最大20回繰り返す
# find_min_cost_combinationでbest_teamを求め、結果のリストに追加
square_history_matrix = [[value ** 2 for value in row] for row in history_matrix]
best_team = find_min_cost_combination(team_combinations, square_history_matrix)
result.append(best_team)
# update_history_matrixでhistory_matrixを更新する
history_matrix = update_history_matrix(history_matrix, best_team)
# もしhistory_matrixのすべての要素が1以上ならbreak
if all(all(value >= 1 for value in row) for row in history_matrix):
break
return result, history_matrix
if __name__ == "__main__":
import argparse
parser = argparse.ArgumentParser(description='Generate teams based on given parameters.')
parser.add_argument('n', type=int, help='The total number of players')
parser.add_argument('k', type=int, help='The number of teams')
parser.add_argument('--max_iter', type=int, default=20, help='The maximum number of iterations')
args = parser.parse_args()
result, history_matrix = generate_teams(args.n, args.k, args.max_iter)
print("result")
for i, team in enumerate(result):
print(f"{i}: {team}")
print("history_matrix")
print(history_matrix)
使い方
まず、gistのコードを任意のPythonファイル名で保存します。ここでは例としてteam_division.pyとします。
次に、tqdmをインストールします（pip install tqdm）。
その後、ターミナルからPythonスクリプトを以下のように実行します。
python team_division.py [n] [k] [--max_iter max_iter]
nはチームの総人数で、kはチームの数を示します。kは各チームの人数ではなく、チームの数であることに注意してください。
例えば、12人を3つのチームに分けたい場合は、n=12, k=3となります。
max_iterは、nが大きい場合に無限ループに陥るのを防ぐための安全装置で、デフォルト値は20です。
nが15以下であれば、20回の繰り返しで十分です。
実行結果は以下のようになります。
python team_division.py 12 3
result
0: [[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11]]
1: [[0, 1, 4, 8], [2, 5, 6, 9], [3, 7, 10, 11]]
2: [[0, 2, 4, 10], [1, 5, 7, 9], [3, 6, 8, 11]]
3: [[0, 3, 5, 8], [1, 6, 7, 10], [2, 4, 9, 11]]
4: [[0, 1, 6, 11], [2, 5, 8, 10], [3, 4, 7, 9]]
5: [[0, 6, 9, 10], [1, 3, 4, 5], [2, 7, 8, 11]]
6: [[0, 5, 7, 11], [1, 2, 3, 9], [4, 6, 8, 10]]
history_matrix
[[1, 3, 2, 2, 2, 2, 2, 1, 2, 1, 2, 2], [3, 1, 2, 3, 2, 2, 2, 2, 1, 2, 1, 1], [2, 2, 1, 2, 2, 2, 1, 1, 2, 3, 2, 2], [2, 3, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2], [2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1], [2, 2, 2, 2, 2, 1, 2, 3, 2, 2, 1, 1], [2, 2, 1, 1, 2, 2, 1, 2, 2, 2, 3, 2], [1, 2, 1, 2, 2, 3, 2, 1, 1, 2, 2, 3], [2, 1, 2, 2, 2, 2, 2, 1, 1, 1, 3, 3], [1, 2, 3, 2, 2, 2, 2, 2, 1, 1, 2, 2], [2, 1, 2, 1, 2, 1, 3, 2, 3, 2, 1, 2], [2, 1, 2, 2, 1, 1, 2, 3, 3, 2, 2, 1]]
resultはチームの分け方を示しています。例えば、n=12, k=3の場合、6回チーム分けを行うと、全員が少なくとも1回は同じチームになることができます。
history_matrixは見た目が複雑ですが、各ペアが同じチームになった回数を示しています。最大値が3であるため、同じチームになる回数に多少の偏りが生じるのは避けられませんが、最大でも3回までなので、悪くない結果だと思います。最大2回に抑えることができるかは不明ですが、3回で最善を尽くしているように感じます。
おわりに
最初は解き方がすぐ見つかるかと思ったのですが、意外と難しかったです。結局、一般的な解法を諦め、nが少ないことを前提に総当りで解を得ました。今回は特定の場面で使いたかっただけなので、目的は果たせました。
今後の発展としては、以下のようなことが考えられます。
- 過去に同じチームになったかどうかだけでなく、属性がなるべく重ならないようにしたい場合は、history_matrixを調整することで比較的簡単に実現できると思います。
- nを増やしたい場合は、やきなまし法のように初期値から少しずつ調整していく手法が必要になるかもしれません。