はじめに

あるスポーツのトーナメント戦を8カ国で行います。4試合づつ7日間の試合を行うとします。
前評判の人気順位がわかっているものとします。
なるべく、人気の高いペアの試合を後半にするようにして、最後までハラハラするような日程を作成してみましょう。

この問題を組合せ最適化で解いてみます。

定式化

変数を、国1、国2、日ごとに、その組合せを"選ぶ選ばない"を表す0-1変数とします。

また、変数に対応する、"2国(i,j)のある日(k)の試合の重み"を以下のようにします。この重みの和を最大化することにより、"あとの方の順位の小さい国同士の試合"を優先するようになります。
$$重み = \frac{2^k}{iの順位 \times jの順位}$$

最大化	$\sum_i{重み_i x_i}$	重みの総和
変数	$x_i \in \{0, 1\} ~ ~ \forall i \in 候補$	その候補を選択するかどうか
制約条件	$\sum_{i \in j,kの組~~~~~}{x_i} = 1 ~ ~ \forall j,k \in \mbox{国}$	同じ組は1つ
制約条件	$\sum_{i \in 国jを含むk日目~~~~~~~~~~~~~}{x_i} = 1 ~ ~ \forall j \in \mbox{国}, \forall k \in \mbox{日}$	同国、同日は1つ

この問題は、スケジューリング問題の一種です。

Pythonでやってみる

まずは、組合せの表を作成します。

python3

import pandas as pd
from itertools import combinations, product
from pulp import *
ss = 'イタリア オランダ 日本 韓国 タイ ドミニカ共和国 ペルー カザフスタン'.split()
rnk = {s:(i+1) for i, s in enumerate(ss)} # 国名→順位
a = pd.DataFrame([(i, j, k, 2**k/rnk[i]/rnk[j]) for i, j in combinations(ss, 2)
                  for k in range(7)], columns='国1 国2 日 重み'.split())
a[:3]
>>>
       国1    国2    日  重み
0  イタリア  オランダ  0  0.5
1  イタリア  オランダ  1  1.0
2  イタリア  オランダ  2  2.0

定式化して解いてみましょう。

python3

m = LpProblem(sense=LpMaximize) # 数理モデル
a['Var'] = [LpVariable('v%d'%i, cat=LpBinary) for i in a.index] # 変数
m += lpDot(a.重み, a.Var) # 目的関数
for _, b in a.groupby(['国1', '国2']):
    m += lpSum(b.Var) == 1 # 同じ組は1つ
for s, i in product(ss, range(7)):
    # 同国、同日は1つ
    m += lpSum(a.query('(国1=="{0}" | 国2=="{0}") & 日=={1}'.format(s, i)).Var) == 1
m.solve() # 求解
a['Val'] = a.Var.apply(value) # 結果
# 表示
for i, b in a.groupby('日'):
    print(i+1, '日目 ')
    for _, r in b[b.Val > 0].iterrows():
        print(' %*s - %s'%(8-len(r.国1), r.国1, r.国2))
>>>
1 日目 
 イタリア - カザフスタン
 オランダ - ペルー
     日本 - ドミニカ共和国
     韓国 - タイ
2 日目 
 イタリア - ペルー
 オランダ - カザフスタン
     日本 - タイ
     韓国 - ドミニカ共和国
3 日目 
 イタリア - ドミニカ共和国
 オランダ - タイ
     日本 - カザフスタン
     韓国 - ペルー
4 日目 
 イタリア - タイ
 オランダ - ドミニカ共和国
     日本 - ペルー
     韓国 - カザフスタン
5 日目 
 イタリア - 韓国
 オランダ - 日本
     タイ - カザフスタン
 ドミニカ共和国 - ペルー
6 日目 
 イタリア - 日本
 オランダ - 韓国
     タイ - ペルー
 ドミニカ共和国 - カザフスタン
7 日目 
 イタリア - オランダ
     日本 - 韓国
     タイ - ドミニカ共和国
   ペルー - カザフスタン

各日の日程が出力されました。

他の方法としては、前半に戦力差のある組合せ、後半に拮抗した戦力差の組合せというのもあるかもしれません。

おまけ

一時的に、私の直近のPython関連の投稿を、Arukasで実行できるようにしています。

https://qiita-jupyter.arukascloud.io/
- 各記事を開いた後で、セルを選択後、Shiftキーを押しながらEnterキーを押すと、実行できます。
上記の元イメージです。
- https://hub.docker.com/r/tsutomu7/qiita-jupyter/

以上

ハラハラするトーナメントの日程を求めよう

はじめに

定式化

Pythonでやってみる

おまけ