体育祭の写真選択

これなに

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

方針

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

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

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

Pythonでやってみる

写真データの作成

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

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行

	写真	生徒
0	写真001	{生徒04, 生徒15, 生徒18, 生徒09, 生徒11, 生徒14, 生徒19}
1	写真002	{生徒04, 生徒03}
2	写真003	{生徒09, 生徒06, 生徒08, 生徒07, 生徒17}

解く

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

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名

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

python3

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

	写真	生徒	x	rx
0	写真001	{生徒04, 生徒15, 生徒18, 生徒09, 生徒11, 生徒14, 生徒19}	v0122	1
11	写真012	{生徒07, 生徒10, 生徒18, 生徒09, 生徒02, 生徒19}	v0133	1
13	写真014	{生徒03, 生徒06, 生徒18, 生徒09, 生徒02, 生徒12, 生徒16}	v0135	1

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

python3

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

クレーム対応

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

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

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枚のままとなった。今度は、満足してもらえたようだ。

以上