体育祭の写真選択

# これなに
1年1組のあなたは、体育祭の様子を記した冊子を作成することになった。1年1組の20人の生徒から5枚ずつ、計100枚の写真を預かった。
さて、どの写真を選ぼうか？

# 方針
生徒やPTAに聞いてみたところ

- 各生徒の写っている枚数(被写体数とよぶことにする)が少ない人がいないようにしたい。
- 上の条件を満たした上で、たくさん写っているのがよい。

なお、写真は20枚以内に収めなければいけない。

# Pythonでやってみる

## 写真データの作成
写真データ(どの写真に誰が写っているか)を作成する。

```py3:python3
import numpy as np, pandas as pd
ni, nj, nu = 20, 100, 20 # 生徒数, 写真数, 選択する写真数
生徒s = ['生徒%.2d'%i for i in range(1,ni+1)]
np.random.seed(1)
mkst = lambda: set(np.random.choice(生徒s, max(1,int(np.random.normal(4,2))), False))
a = pd.DataFrame([('写真%.3d'%j, mkst()) for j in range(1,nj+1)],
    columns=['写真', '生徒'])
a[:3] # 最初の3行
```

<table>
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>写真</th>
      <th>生徒</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>写真001</td>
      <td>{生徒04, 生徒15, 生徒18, 生徒09, 生徒11, 生徒14, 生徒19}</td>
    </tr>
    <tr>
      <th>1</th>
      <td>写真002</td>
      <td>{生徒04, 生徒03}</td>
    </tr>
    <tr>
      <th>2</th>
      <td>写真003</td>
      <td>{生徒09, 生徒06, 生徒08, 生徒07, 生徒17}</td>
    </tr>
  </tbody>
</table>

## 解く
目的関数は、適当に「10×最小被写体数＋総被写体数」にしてみよう。

```py3:python3
from pulp import *
from ortoolpy import addvar, addvars, addbinvars
m = LpProblem(sense=LpMaximize) # 数理モデル
a['x'] = addbinvars(nj) # 写真ごとの選択
y      = addvars(ni)    # 生徒ごとの被写体数
ymin   = addvar()       # 最小被写体数
m += 10*ymin + lpSum(y) # 目的関数
m += lpSum(a.x) == nu # 選択写真数
for yi,st in zip(y,生徒s):
    m += yi == lpSum(r.x for _,r in a.iterrows()
                     if st in r.生徒) # 各生徒の被写体数
    m += ymin <= yi
%time m.solve() # 求解
a['rx'] = np.vectorize(value)(a.x).astype(int) # 結果
ry      = np.vectorize(value)(y  ).astype(int) # 結果
print('%s 最小%d名 平均%.2f名'%
    (LpStatus[m.status], value(ymin), sum(ry)/ni))
>>>
Wall time: 39.2 ms
Optimal 最小5名 平均6.25名
```

選んだ写真を見てみよう。

```py3:python3
a[a.rx>0][:3] # 最初の3行
```

<table>
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>写真</th>
      <th>生徒</th>
      <th>x</th>
      <th>rx</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>写真001</td>
      <td>{生徒04, 生徒15, 生徒18, 生徒09, 生徒11, 生徒14, 生徒19}</td>
      <td>v0122</td>
      <td>1</td>
    </tr>
    <tr>
      <th>11</th>
      <td>写真012</td>
      <td>{生徒07, 生徒10, 生徒18, 生徒09, 生徒02, 生徒19}</td>
      <td>v0133</td>
      <td>1</td>
    </tr>
    <tr>
      <th>13</th>
      <td>写真014</td>
      <td>{生徒03, 生徒06, 生徒18, 生徒09, 生徒02, 生徒12, 生徒16}</td>
      <td>v0135</td>
      <td>1</td>
    </tr>
  </tbody>
</table>

生徒ごとの被写体数を確認する。

```py3:python3
%matplotlib inline
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'IPAexGothic'
plt.plot(ry)
plt.xlabel('生徒')
plt.title('被写体数');
```

![image](https://qiita-image-store.s3.amazonaws.com/0/13955/69331adf-058c-317a-aba1-0b6531bc30a9.png)

# クレーム対応
選んだ写真を見てもらうと、早速、「自分の提出した写真も選んでほしい」とクレームが来た。

**「各生徒の提出した写真から1枚ずつ選ぶこと」**を制約条件に追加して再実行してみよう。

```py3:python3
from more_itertools import chunked
m = LpProblem(sense=LpMaximize) # 数理モデル
a['x'] = addbinvars(nj) # 写真ごとの選択
y      = addvars(ni)    # 生徒ごとの被写体数
ymin   = addvar()       # 最小被写体数
m += 10*ymin + lpSum(y) # 目的関数
m += lpSum(a.x) == nu # 選択写真数
for yi,st in zip(y,生徒s):
    m += yi == lpSum(r.x for _,r in a.iterrows()
                     if st in r.生徒) # 各生徒の被写体数
    m += ymin <= yi
for t in chunked(a.iterrows(), 5): # 各生徒提出の5枚組
    m += lpSum(r.x for _,r in t) == 1 # 5枚組から1枚選ぶ
%time m.solve() # 求解
a['rx'] = np.vectorize(value)(a.x).astype(int) # 結果
ry      = np.vectorize(value)(y  ).astype(int) # 結果
print('%s 最小%d名 平均%.2f名'%
    (LpStatus[m.status], value(ymin), sum(ry)/ni))
>>>
Wall time: 54.1 ms
Optimal 最小5名 平均5.70名
```

最小被写体数は、5枚のままとなった。今度は、満足してもらえたようだ。

以上