※ このケーススタディはフィクションです。実際の研究室配属に用いたことはありません。
状況を整理しましょう
研究室名
# 研究室名
labs = list("ABCDEFG")
labs
['A', 'B', 'C', 'D', 'E', 'F', 'G']
各研究室の最低配属数
# 各研究室の最低配属数
min_assign = [2 for x in range(len(labs))]
min_assign
[2, 2, 2, 2, 2, 2, 2]
各研究室の最大配属数
# 各研究室の最大配属数
max_assign = [4 for x in range(len(labs))]
max_assign
[4, 4, 4, 4, 4, 4, 4]
学生ID
# 学生ID
n_students = 20
students = [x + 1 for x in range(n_students)]
students
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
学生の成績順位
# 学生の成績順位
import random
grades = [x + 1 for x in range(n_students)]
random.shuffle(grades)
grades
[9, 4, 13, 14, 7, 17, 5, 2, 10, 1, 19, 16, 18, 20, 3, 15, 12, 6, 8, 11]
研究室配属希望順位調査
# 研究室配属希望順位調査
questionnaire = []
for x in range(n_students):
hope = [x + 1 for x in range(len(labs))]
random.shuffle(hope)
if x > 0 and random.random() < 0.1: # 希望順位が同じという人も作る
hope = questionnaire[x - 1]
questionnaire.append(hope)
questionnaire
[[2, 7, 3, 5, 4, 6, 1],
[2, 6, 1, 7, 3, 4, 5],
[4, 7, 6, 5, 2, 1, 3],
[6, 3, 2, 4, 1, 7, 5],
[2, 5, 4, 3, 7, 1, 6],
[3, 7, 2, 6, 5, 1, 4],
[1, 7, 3, 2, 6, 5, 4],
[4, 1, 7, 3, 6, 2, 5],
[7, 6, 4, 3, 1, 2, 5],
[5, 3, 4, 7, 1, 6, 2],
[3, 2, 7, 4, 6, 1, 5],
[6, 7, 5, 4, 1, 2, 3],
[6, 7, 5, 4, 1, 2, 3],
[2, 3, 7, 5, 1, 4, 6],
[7, 3, 5, 1, 6, 4, 2],
[6, 5, 7, 4, 3, 2, 1],
[2, 3, 1, 5, 6, 4, 7],
[4, 2, 1, 6, 7, 5, 3],
[6, 2, 7, 4, 1, 3, 5],
[2, 5, 4, 6, 1, 3, 7]]
ランダムに配属を決める
# ランダムに配属を決める
assignment = [[] for x in range(len(labs))]
rand_stu = [x for x in range(n_students)]
random.shuffle(rand_stu)
lab = 0
for stu in rand_stu:
assignment[lab % len(labs)].append(stu)
lab += 1
assignment
[[8, 13, 6],
[1, 5, 17],
[18, 16, 3],
[9, 2, 11],
[12, 10, 14],
[0, 4, 15],
[19, 7]]
配属の結果、誰が第何希望か
def resulted(assignment, questionnaire):
return [[questionnaire[stu][i] for j, stu in enumerate(lab)] for i, lab in enumerate(assignment)]
resulted(assignment, questionnaire)
[[7, 2, 1], [6, 7, 2], [7, 1, 2], [7, 5, 4], [1, 6, 6], [6, 1, 2], [7, 5]]
全体としての不満の大きさ
def fuman(assignment, questionnaire):
ary = resulted(assignment, questionnaire)
return sum([sum(x) - len(x) for x in ary])
fuman(assignment, questionnaire)
65
成績の良い者から優先的に決める（最低配属数を考慮しない）
# 成績の良い者から優先的に、希望研究室を決めていく方法（最低配属数を考慮しない）
assignment = [[] for x in range(len(labs))]
for i in range(len(students)):
stu = grades.index(i + 1) # 成績順位 i 番の学生
que = questionnaire[stu] # 成績順位 i 番の学生の希望順位
for j in range(len(labs)):
lab = que.index(j + 1) # 希望順位 j の研究室
if len(assignment[lab]) < max_assign[lab]:
assignment[lab].append(stu)
break
assignment
[[6, 13],
[7, 10],
[1, 17, 16, 3],
[14],
[9, 18, 8, 19],
[4, 2, 11, 5],
[0, 15, 12]]
配属の結果、誰が第何希望か
resulted(assignment, questionnaire)
[[1, 2], [1, 2], [1, 1, 1, 2], [1], [1, 1, 1, 1], [1, 1, 2, 1], [1, 1, 3]]
全体としての不満の大きさ
fuman(assignment, questionnaire)
6
成績の良い者から優先的に決める（最低配属数を考慮する）
まず最低配属数を埋める
# 成績の良い者から優先的に、希望研究室を決めていく方法（まず最低配属数を埋める）
assignment = [[] for x in range(len(labs))]
assigned_students = []
for i in range(len(students)):
stu = grades.index(i + 1) # 成績順位 i 番の学生
que = questionnaire[stu] # 成績順位 i 番の学生の希望順位
for j in range(len(labs)):
lab = que.index(j + 1) # 希望順位 j の研究室
if len(assignment[lab]) < min_assign[lab]:
assignment[lab].append(stu)
assigned_students.append(stu)
break
assignment
[[6, 19], [7, 16], [1, 17], [14, 3], [9, 18], [4, 8], [0, 2]]
assigned_students
[9, 7, 14, 1, 6, 17, 4, 18, 0, 8, 19, 16, 2, 3]
未配属の学生を割り当てる
# 成績の良い者から優先的に、希望研究室を決めていく方法（未配属の学生を割り当てる）
for i in range(len(students)):
stu = grades.index(i + 1) # 成績順位 i 番の学生
que = questionnaire[stu] # 成績順位 i 番の学生の希望順位
if stu in assigned_students:
continue
for j in range(len(labs)):
lab = que.index(j + 1) # 希望順位 j の研究室
if len(assignment[lab]) < max_assign[lab]:
assignment[lab].append(stu)
assigned_students.append(stu)
break
assignment
[[6, 19, 13],
[7, 16],
[1, 17],
[14, 3],
[9, 18, 11, 12],
[4, 8, 5, 10],
[0, 2, 15]]
配属の結果、誰が第何希望か
resulted(assignment, questionnaire)
[[1, 2, 2], [1, 3], [1, 1], [1, 4], [1, 1, 1, 1], [1, 2, 1, 1], [1, 3, 1]]
全体としての不満の大きさ
fuman(assignment, questionnaire)
10
実際のところ
人気が集中する研究室とか、全く人気のない研究室とか、いろいろあるので難しいですね(´・ω・`)