※ このケーススタディはフィクションです。実際の研究室配属に用いたことはありません。

状況を整理しましょう

研究室名

# 研究室名
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)

成績の良い者から優先的に決める（最低配属数を考慮しない）

# 成績の良い者から優先的に、希望研究室を決めていく方法（最低配属数を考慮しない）
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)

成績の良い者から優先的に決める（最低配属数を考慮する）

まず最低配属数を埋める

# 成績の良い者から優先的に、希望研究室を決めていく方法（まず最低配属数を埋める）
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)

実際のところ

人気が集中する研究室とか、全く人気のない研究室とか、いろいろあるので難しいですね(´・ω・`)