学生実験のテーマ割当を自動化するPythonスクリプト

# はじめに

学生実験におけるテーマ割り当ては、学生の希望をなるべく反映させつつ、テーマごとの定員を超えないように行う必要があります。本記事では、70名の学生を6つのテーマに割り振るためのスクリプトを、擬似的な希望リストの作成から実際の割り振りまでの流れを解説します。割り振りの平等性を保つため、ランダム要素を取り入れたアルゴリズムを採用しています。

google colab 上での実行例は下記に掲載しています。

https://colab.research.google.com/drive/1mYVA5XZUmUM279qW97722bOyGeujBnLb?usp=sharing

## 概要
この割り振りプログラムは2つのステップで構成されています。
1. 学生の擬似的な希望リストの作成
2. 学生をテーマに割り振る

各テーマの定員（11〜12名）を設定し、希望順に従って学生をテーマに割り当てますが、全ての希望が満たされない場合にはランダムにテーマが割り当てられる仕組みを導入しています。

## 手順 1: 擬似的な希望リストの作成

まず、学生70名分の擬似的な希望リストを生成します。各学生には、1〜4番目の希望をテーマ6つ（光、真空、計算機、放射線、半導体、電子回路）からランダムに割り振ります。

以下のスクリプトでは、ランダムに生成した日本の姓と名前を使用し、希望リストをCSVファイルに保存します。

```python: qiita_gen_student_kibou.py
#!/usr/bin/python
# -*- coding: utf-8 -*-

import pandas as pd
import random
import matplotlib.pyplot as plt
from matplotlib import font_manager

# フォントパスを指定（Macの場合、ヒラギノを例として）
font_path = "/System/Library/Fonts/ヒラギノ丸ゴ ProN W4.ttc"
jp_font = font_manager.FontProperties(fname=font_path)

# 名前のリスト
first_names_male = ['太郎', '一郎', '健太', '大輔', '翔太', '悠真', '陽翔', '拓海', '颯太', '大和']
first_names_female = ['花子', '美咲', '結衣', '陽菜', '美優', '杏奈', 'さくら', '莉子', '詩織', '彩花']
last_names = ['佐藤', '鈴木', '高橋', '田中', '伊藤', '山本', '中村', '小林', '加藤', '吉田']

# テーマリスト
themes = ['光', '真空', '計算機', '放射線', '半導体', '電子回路']
num_students = 70

# ランダムに名前を生成する関数
def generate_random_name():
    last_name = random.choice(last_names)
    if random.random() > 0.5:
        first_name = random.choice(first_names_male)
    else:
        first_name = random.choice(first_names_female)
    return f"{last_name} {first_name}"

# ランダムに希望を割り振る
data = {
    'ID': [f"student_{i:03d}" for i in range(1, num_students + 1)],
    'Name': [generate_random_name() for _ in range(num_students)],
    '1st': [random.choice(themes) for _ in range(num_students)],
    '2nd': [random.choice(themes) for _ in range(num_students)],
    '3rd': [random.choice(themes) for _ in range(num_students)],
    '4th': [random.choice(themes) for _ in range(num_students)]
}

# データフレームに変換し、CSVに保存
df_students = pd.DataFrame(data)
df_students.to_csv('student_preferences.csv', index=False)
```

実行する場合は、ターミナルなどで、

``` bash:
python qiita_gen_student_kibou.py
``` 

で実行してください。その結果、

``` bash:
%head -5 student_preferences.csv                                         ID,Name,1st,2nd,3rd,4th
student_001,山本 彩花,半導体,半導体,計算機,電子回路
student_002,山本 翔太,光,光,真空,光
student_003,鈴木 拓海,放射線,半導体,半導体,放射線
...
```

のように、csv ファイルが生成されていれば ok です。

:::note info
CSVファイルのヘッダーは、`ID,Name,1st,2nd,3rd,4th` というスタイルで書かれていることが前提で、次のプログラムが動きます。
:::



## 手順 2: 割り振りアルゴリズム

次に、希望リストを基にテーマ割り振りを行います。定員に達したテーマにはこれ以上割り振らないようにし、全ての希望が満たされない場合はランダムに残りのテーマに割り振ります。

以下のスクリプトは、割り振り結果をCSVファイルとして出力し、テーマごとの割り当て数を棒グラフで可視化します。

```python
#!/usr/bin/python
# -*- coding: utf-8 -*-

import pandas as pd
import random
import argparse
import matplotlib.pyplot as plt
from matplotlib import font_manager

# フォント設定
font_path = "/System/Library/Fonts/ヒラギノ丸ゴ ProN W4.ttc"
jp_font = font_manager.FontProperties(fname=font_path)

# コマンドライン引数の処理
def parse_arguments():
    parser = argparse.ArgumentParser(description='テーマ割り当てプログラム')
    parser.add_argument('csv_file', help='入力CSVファイルのパス')
    return parser.parse_args()

# CSVデータの読み込み
def load_data(csv_file):
    df = pd.read_csv(csv_file)
    return df

# テーマ定員の設定
def set_theme_capacities():
    return {'光': 12, '真空': 12, '計算機': 11, '放射線': 12, '半導体': 11, '電子回路': 12}

# 割り振りアルゴリズム
def assign_to_themes_with_random(df, capacities):
    assignment = {}
    unassigned = []
    shuffled_df = df.sample(frac=1).reset_index(drop=True)

    for i, row in shuffled_df.iterrows():
        choice = row['1st']
        if capacities[choice] > 0:
            if choice not in assignment:
                assignment[choice] = []
            assignment[choice].append(row['ID'])
            capacities[choice] -= 1
        else:
            unassigned.append((row['ID'], row['2nd'], row['3rd'], row['4th']))

    random.shuffle(unassigned)
    for id_, second, third, fourth in unassigned:
        assigned = False
        for choice in [second, third, fourth]:
            if capacities[choice] > 0:
                assignment[choice].append(id_)
                capacities[choice] -= 1
                assigned = True
                break

        if not assigned:
            available_themes = [theme for theme, cap in capacities.items() if cap > 0]
            random_choice = random.choice(available_themes)
            assignment[random_choice].append(id_)
            capacities[random_choice] -= 1

    return assignment

# メイン関数
def main():
    args = parse_arguments()
    df_students = load_data(args.csv_file)
    capacities = set_theme_capacities()
    assignments_with_random = assign_to_themes_with_random(df_students, capacities)

    assignment_results = []
    for student_id in df_students['ID']:
        for theme, students in assignments_with_random.items():
            if student_id in students:
                assignment_results.append(theme)
                break

    df_students['Assigned Theme'] = assignment_results
    output_file = 'student_preferences_result.csv'
    df_students.to_csv(output_file, index=False)
    print(f"結果を保存しました: {output_file}")

    theme_assignments_with_random = {theme: len(students) for theme, students in assignments_with_random.items()}
    
    plt.bar(theme_assignments_with_random.keys(), theme_assignments_with_random.values(), color='orange')
    plt.axhline(y=12, color='r', linestyle='--', label="最大定員 (12)")
    plt.axhline(y=11, color='g', linestyle='--', label="最大定員 (11)")
    plt.xlabel('テーマ', fontproperties=jp_font)
    plt.ylabel('割り当てられた学生数', fontproperties=jp_font)
    plt.title('学生のテーマ割り当て（ランダム割り当て付き）', fontproperties=jp_font)
    plt.xticks(fontproperties=jp_font)
    plt.legend(prop=jp_font)
    outputfile = "wariate.png"
    plt.savefig(outputfile)
    print(f"{outputfile} is created.")
    plt.show()

if __name__ == "__main__":
    main()
```

実行するには、

``` 
$python qiita_assign_student_themes.py student_preferences.csv           CSV file with results saved successfully: student_preferences_result.csv
wariate.png is created.
             ID    Name  1st  2nd   3rd   4th Assigned Theme
0   student_001   山本 彩花  半導体  半導体   計算機  電子回路            半導体
1   student_002   山本 翔太    光    光    真空     光              光
2   student_003   鈴木 拓海  放射線  半導体   半導体   放射線            放射線
3   student_004   高橋 花子  放射線  半導体   放射線     光            放射線
4   student_005   鈴木 莉子    光  半導体   放射線   計算機              光
..          ...     ...  ...  ...   ...   ...            ...
65  student_066   山本 一郎  放射線  計算機     光  電子回路            放射線
66  student_067   田中 彩花    光   真空  電子回路     光              光
67  student_068   山本 花子   真空  放射線  電子回路   放射線             真空
68  student_069   鈴木 太郎  放射線  計算機   放射線    真空             真空
69  student_070  山本 さくら    光    光   半導体   計算機              光

[70 rows x 7 columns]
``` 

のように表示されて、次のようなグラフが生成されれば ok です。

![スクリーンショット 2024-09-21 1.15.32.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/179652/eccf3513-ae9c-2e3a-6a2e-ca1d56299637.png)

結果は、`student_preferences_result.csv` というファイルに CSVファイルで保存されます。

:::note warn
フォント設定で、`font_path = "/System/Library/Fonts/ヒラギノ丸ゴ ProN W4.ttc"` は mac の場合はこの場所に ttc ファイルがあると思います。windows や linux の場合は、書き換える必要があります。
:::

### 日本語対応

日本語が正しく表示されない問題は、フォントやエンコーディング設定の問題である可能性が高いです。特に、matplotlibを使用して日本語を表示する際には、デフォルトのフォントが日本語をサポートしていないため、**日本語対応のフォント**を指定する必要があります。

### 解決方法

1. **日本語フォントを指定する**  
   matplotlibで日本語を扱うには、日本語に対応したフォントを明示的に設定する必要があります。例えば、`IPAexGothic`や`Noto Sans CJK JP`などのフォントが一般的です。

2. **matplotlibのフォント設定の追加**  
   以下のように、matplotlibで日本語フォントを指定することで解決できます。

```python
import matplotlib.pyplot as plt
from matplotlib import font_manager

# 日本語フォントを指定 (IPAexGothicを使う場合)
# 使用するフォントパスを指定
font_path = '/usr/share/fonts/opentype/ipafont-gothic/ipagp.ttf'  # 例：Linuxの場合
# Windowsの場合は、"C:/Windows/Fonts/msgothic.ttc" などに変更

# フォントプロパティの設定
jp_font = font_manager.FontProperties(fname=font_path)
```
### ポイント：
1. **`fontproperties`を設定**：`xlabel`や`ylabel`、`title`のところで`fontproperties=jp_font`を指定しています。これにより、日本語フォントが使われるようになります。
2. **フォントのパス**：`font_path`で指定するフォントのパスは、OSに依存します。Linux、Mac、Windowsそれぞれに適切なフォントパスを設定してください。
   - **Linux**: 通常、`/usr/share/fonts/`以下に日本語フォントがあることが多いです。
   - **Windows**: `C:/Windows/Fonts/`以下に`msgothic.ttc`などのフォントがあります。
   - **Mac**: `Library/Fonts/`などのパスにフォントがあります。

### 必要なフォントがインストールされていない場合：
- 日本語フォントがインストールされていない場合、`IPAexGothic`や`Noto Sans CJK JP`などをインストールする必要があります。

```bash
# Linuxでのフォントインストール例
sudo apt-get install fonts-ipafont
```

これで、matplotlibのグラフやテキストで日本語が正常に表示されるはずです。

## アルゴリズムの説明

割り振りのアルゴリズムでは、以下の2つのポイントが特に重要です。
1. **公平性の確保**：第1希望から第4希望までを順番に確認し、各学生が可能な限り希望通りのテーマに割り当てられるようにしています。また、希望が全て満たされない場合には、定員に空きのあるテーマにランダムで割り当てることで、均等に割り振りが行われるようにしています。
2. **定員の制約**：テーマごとに最大定員を設定しており、これを超えた割り振りは行わないようにしています。

割り当てのところで、`assignment`と`capacities`の使われ方は重要になりますので、説明を以下に示します。

### `assignment`の役割

`assignment`は、**各テーマに割り当てられた学生のIDを管理する辞書**です。この辞書はテーマ（例: "光"や"真空"）をキーに持ち、そのテーマに割り当てられた学生のIDリストを値として保持します。

たとえば、次のように`assignment`にデータが格納されます。

```python
assignment = {
    '光': ['student_001', 'student_002'],
    '真空': ['student_003', 'student_004'],
    # ...
}
```

このように、各テーマごとに誰が割り当てられたかを追跡できるようになっています。  
プログラムでは、まず第1希望から学生をテーマに割り当て、希望が満たされない場合には第2〜第4希望やランダムで割り当てを行っています。

```python
# 割り当てる学生が決まった場合に、`assignment`に追加する処理
if choice not in assignment:
    assignment[choice] = []  # まだテーマに割り当てられた学生がいない場合、空のリストを作成
assignment[choice].append(row['ID'])  # 学生のIDをそのテーマに追加
```

### 日本語フォント

**`ttc`**（TrueType Collection）や **`ttf`**（TrueType Font）ファイルは、**フォントの定義や情報**が書かれているファイル形式です。これらのフォントファイルには、フォントの形状やスタイル、文字セットに関する情報が含まれています。

### 1. **`ttf`（TrueType Font）ファイル**
   - **TrueTypeフォント（TTF）**は、1980年代にAppleとMicrosoftが共同で開発したフォント形式です。1つのフォントスタイル（例えば「ヒラギノ角ゴシック W3」など）の定義が含まれています。
   - `ttf`ファイルには、文字の形状（アウトライン）がベクターデータとして保存されており、サイズに関係なく高品質な描画が可能です。
   - フォントの**文字セット**（アルファベット、漢字、仮名など）、**ヒンティング情報**（表示を美しくするためのガイドライン）、**メタデータ**（フォント名、ライセンス情報など）も含まれます。

### 2. **`ttc`（TrueType Collection）ファイル**
- **TrueType Collection（TTC)** は、複数のTrueTypeフォント（`ttf`）を1つのファイルにまとめた形式です。これにより、ファイルサイズを削減できるため、同じフォントファミリ（例えば「ヒラギノ角ゴシック W3」「ヒラギノ角ゴシック W6」など）が複数含まれる場合によく使われます。
   - 複数のフォントスタイルが一つのファイルに含まれるため、`ttc`は複数の異なるフォントを効率的に格納するための形式です。例えば、同じフォントファミリ内の異なるウェイトやスタイル（太字、斜体など）を一つにまとめることができます。

見つからない場合は、`locate` などのコマンドで、`ttf` や `ttc` ファイルを検索して、指定して使いましょう。

### `capacities`の役割

`capacities`は、**各テーマの定員を管理する辞書**です。各テーマに割り当てられる最大の学生数が設定されており、これを超えないように管理されています。定員が一杯になったテーマには、これ以上学生を割り当てられません。

たとえば、次のようにテーマごとの定員が設定されています。

```python
capacities = {
    '光': 12,
    '真空': 12,
    '計算機': 11,
    '放射線': 12,
    '半導体': 11,
    '電子回路': 12
}
```

この定員は、各学生がテーマに割り当てられるたびに1ずつ減らされ、最終的に0になるとそのテーマは「満員」になり、それ以上の割り当てができなくなります。

```python
if capacities[choice] > 0:  # 定員が残っているか確認
    capacities[choice] -= 1  # 割り当てが行われた場合、定員を1減らす
```

# googlecolab で実行する場合

Google Colabでこのプログラムを動かせるように、いくつかの修正が必要です。特に、フォント設定やCSVファイルの扱いなどに対応します。

https://colab.research.google.com/drive/1mYVA5XZUmUM279qW97722bOyGeujBnLb?usp=sharing

を参考にしてください。

# アルゴリズムの詳細な解説

### 1. 関数の入力
この関数は2つの引数を受け取ります：
- **`df`**: 学生の希望リストを持つ `DataFrame`。各学生のIDと第1〜第4希望のテーマが含まれています。
- **`capacities`**: 各テーマの最大定員を指定した辞書。例えば、`{'光': 12, '真空': 12, '計算機': 11, ...}` のように、テーマごとの定員が定義されています。

### 2. ステップ 1: 第1希望での割り当て
まず、各学生の第1希望（`1st`）テーマに割り当てを試みます。もしテーマの定員に余裕があれば、その学生は第1希望に割り当てられ、定員が1減少します。

- **定員が残っている場合**:
  - 学生をそのテーマに割り当てます。
  - 定員を1減らします。
- **定員が満員の場合**:
  - その学生は第1希望に割り当てられず、「未割り当てリスト」に追加されます。このリストには、次に第2希望を試みるべき学生の情報が入ります。

入力データをシャッフルすることで、入力データの順番には依存しないようにしています。

### 3. ステップ 2: 第2〜第4希望での割り当て

第1希望で割り当てられなかった学生については、第2希望（`2nd`）、第3希望（`3rd`）、第4希望（`4th`）を順に割り当てを試みます。

- 各学生について、まだ定員に余裕があるテーマを順に探します。
  - 定員に余裕があるテーマが見つかった場合、そのテーマに割り当て、定員を1減らします。
  - 全ての希望が満員だった場合、その学生は依然として「未割り当て」となります。

### 4. ステップ 3: ランダム割り当て

第1〜第4希望全てが定員いっぱいだった学生については、残っているテーマの中からランダムにテーマを選びます。

- **空きのあるテーマを確認**:
  - 定員がまだ残っているテーマのリストを作成します。
  - リストの中からランダムに1つを選び、そのテーマに割り当てます。
  - 定員を1減らします。

これにより、全ての学生がテーマに割り当てられるようになります。

### アルゴリズムの流れ図

1. **第1希望の割り当て**:
   - `for` ループで全ての学生に対して、第1希望のテーマが定員に余裕があるか確認。
   - 定員が残っていれば割り当て、無ければ未割り当てリストに追加。

2. **第2〜第4希望の割り当て**:
   - 未割り当ての学生に対して、順次第2希望→第3希望→第4希望のテーマが定員に余裕があるか確認。
   - 定員が残っていれば割り当て、無ければ次の希望へ。

3. **ランダム割り当て**:
   - 全ての希望が満員だった学生に対して、空いているテーマをランダムに選んで割り当て。

### アルゴリズムの特徴

- **効率的な希望反映**: 学生の希望を第1から第4まで順に試すことで、できる限り希望に沿ったテーマに割り当てようとします。
- **柔軟な対応**: 全ての希望が定員オーバーだった場合でも、ランダムに割り当てを行うことで、全員が必ずテーマに割り当てられます。
- **定員オーバーを防止**: 各テーマの定員を管理し、どの学生も定員を超えることが無いように割り当てを行います。

# まとめ

このように乱数と辞書を使うことで、希望調査の結果を踏まえたテーマ分類の自動化を実現できます。ただし、完璧に動作するか、早く収束するかは、与えられた制約条件が強くなると性能は悪くなりますので、問題に合わせてチューニングすることをおすすめします。