Pythonで研究室配属を決める（フィクションです）

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

# 状況を整理しましょう

## 研究室名

```python
# 研究室名
labs = list("ABCDEFG")
labs
```




    ['A', 'B', 'C', 'D', 'E', 'F', 'G']


## 各研究室の最低配属数

```python
# 各研究室の最低配属数
min_assign = [2 for x in range(len(labs))]
min_assign
```




    [2, 2, 2, 2, 2, 2, 2]


## 各研究室の最大配属数


```python
# 各研究室の最大配属数
max_assign = [4 for x in range(len(labs))]
max_assign
```




    [4, 4, 4, 4, 4, 4, 4]


## 学生ID

```python
# 学生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]


## 学生の成績順位

```python
# 学生の成績順位
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]


## 研究室配属希望順位調査

```python
# 研究室配属希望順位調査
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]]


# ランダムに配属を決める


```python
# ランダムに配属を決める
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
```


```python
assignment
```




    [[8, 13, 6],
     [1, 5, 17],
     [18, 16, 3],
     [9, 2, 11],
     [12, 10, 14],
     [0, 4, 15],
     [19, 7]]


## 配属の結果、誰が第何希望か

```python
def resulted(assignment, questionnaire):
    return [[questionnaire[stu][i] for j, stu in enumerate(lab)] for i, lab in enumerate(assignment)]
```


```python
resulted(assignment, questionnaire)
```




    [[7, 2, 1], [6, 7, 2], [7, 1, 2], [7, 5, 4], [1, 6, 6], [6, 1, 2], [7, 5]]


## 全体としての不満の大きさ

```python
def fuman(assignment, questionnaire):
    ary = resulted(assignment, questionnaire)
    return sum([sum(x) - len(x) for x in ary])
```


```python
fuman(assignment, questionnaire)
```




    65


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

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


```python
assignment
```




    [[6, 13],
     [7, 10],
     [1, 17, 16, 3],
     [14],
     [9, 18, 8, 19],
     [4, 2, 11, 5],
     [0, 15, 12]]



## 配属の結果、誰が第何希望か


```python
resulted(assignment, questionnaire)
```




    [[1, 2], [1, 2], [1, 1, 1, 2], [1], [1, 1, 1, 1], [1, 1, 2, 1], [1, 1, 3]]


## 全体としての不満の大きさ


```python
fuman(assignment, questionnaire)
```




    6


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

## まず最低配属数を埋める

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


```python
assignment
```




    [[6, 19], [7, 16], [1, 17], [14, 3], [9, 18], [4, 8], [0, 2]]




```python
assigned_students
```




    [9, 7, 14, 1, 6, 17, 4, 18, 0, 8, 19, 16, 2, 3]


## 未配属の学生を割り当てる

```python
# 成績の良い者から優先的に、希望研究室を決めていく方法（未配属の学生を割り当てる）
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
```


```python
assignment
```




    [[6, 19, 13],
     [7, 16],
     [1, 17],
     [14, 3],
     [9, 18, 11, 12],
     [4, 8, 5, 10],
     [0, 2, 15]]


## 配属の結果、誰が第何希望か


```python
resulted(assignment, questionnaire)
```




    [[1, 2, 2], [1, 3], [1, 1], [1, 4], [1, 1, 1, 1], [1, 2, 1, 1], [1, 3, 1]]


## 全体としての不満の大きさ


```python
fuman(assignment, questionnaire)
```




    10


# 実際のところ

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