目的
引き分けを許す 1 回総当たり戦を $n$ チームで行ったとき、その結果に表れる勝敗パターンと勝ち点パターンを列挙したい。
サッカーのワールドカップが盛り上がっており、気になったので。
方法
勝敗パターンの列挙
1 回総当たり戦の結果をグラフにより表すことにする。グラフの頂点をチームと見なし、ある試合について勝ちチームから負けチームへと有向辺を 1 本だけ結ぶ。引き分けの場合は辺を結ばない。
これによって得られるグラフたちを全パターン列挙する。また、頂点のラベルを入れ替えても同型なグラフは区別しない。
用語と蛇足
- 向き付けされたグラフ
- 単純な無向グラフのすべての辺を任意の向きの有向辺にしたグラフであり、同じことだが、任意の頂点間の辺は高々 1 本である単純な有向グラフのことを向き付けされた (oriented) グラフと呼ぶ。定訳はないらしい。上記の作業で得られるグラフはこれ。
- トーナメント
- 任意の頂点間に向きを問わず辺が存在する向き付けされたグラフをトーナメントと呼ぶ。総当たり戦に引き分けがない場合に得られるグラフはこれ。 いわゆるトーナメント戦も総当たり戦も英語では tournament らしく、今は後者のことであるが、今回の話にトーナメントはとくに絡まない。
mathworld.wolfram.com
勝ち点パターンの列挙
勝敗パターンに対応する向き付けされたグラフにおいて、ある頂点の出次数と入次数は対応するチームのそれぞれ勝利数と敗北数に等しい。$n$ チームによる 1 回総当たり戦では各チームはいずれも $n-1$ 試合を行うことから、勝利・敗北・引き分けにそれぞれ勝ち点を割り振れば、その総当たり戦の結果として現れる勝ち点配分が計算できる。
具体例
4 チーム 1 回総当たり戦の結果として次の組み合わせ表が得られたとする。
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | ＼ | 勝 | 分 | 勝 |
| 1 | 負 | ＼ | 勝 | 勝 |
| 2 | 分 | 負 | ＼ | 分 |
| 3 | 負 | 負 | 分 | ＼ |
これに対応するグラフは次のようになる。
また、$ n$ チーム 1 回総当たり戦における勝敗パターンの数は OEIS にある。
勝ち点パターンについても OEIS にある。勝ち点については一般的なサッカー形式で、勝利・敗北・引き分けにそれぞれ 3、0、1 が割り振られたもの。
コード
SageMath で書いた。
関数たち。
def oriented_graphs(n): # OEIS: A001174 a = graphs.nauty_geng(str(n)) # Non-isomorphic simple undirected graphs with n vertices return digraphs.nauty_directg(a, options="-o") def point_allocation(graph, *, for_win=3, for_lose=0, for_draw=1): return tuple( sorted( ( for_draw * (graph.num_verts() - 1) + (for_lose - for_draw) * graph.in_degree(v) + (for_win - for_draw) * graph.out_degree(v) for v in graph.vertex_iterator() ), reverse=True, ) ) def by_point_allocation(graphs, *, for_win=3, for_lose=0, for_draw=1): # OEIS: A064626 a = dict() for g in graphs: b = point_allocation(g, for_win=for_win, for_lose=for_lose, for_draw=for_draw) a.setdefault(b, list()) a[b].append(g.copy(immutable=True)) return a
呼び出し例。3 チーム 1 回総当たりでの勝ち点パターンを列挙。
for g in oriented_graphs(3): print(point_allocation(g))
呼び出し結果。
(2, 2, 2) (4, 2, 1) (4, 4, 0) (4, 3, 1) (6, 1, 1) (6, 3, 0) (3, 3, 3)
呼び出し例。1～6 チーム 1 回総当たりでの勝ち点パターン of 勝敗パターン。
for n in range(1, 7): total = {"graph": 0, "alloc": 0} alloc_patterns = by_point_allocation(oriented_graphs(n)) for e in alloc_patterns.keys(): # print(e) for g in alloc_patterns[e]: total["graph"] += 1 # g.show(layout="circular") total["alloc"] += 1 print("%s: %s of %s" % (n, total["alloc"], total["graph"]))
呼び出し結果。
1: 1 of 1 2: 2 of 2 3: 7 of 7 4: 40 of 42 5: 355 of 582 6: 3678 of 21480
