Pythonで同時に成立する部屋移動リクエストの最大数を求めるプログラム

寮には0からn-1までの番号が付けられたn個の部屋があるとします。各部屋の学生は別の部屋へ引っ越したいと考えており、そのために複数の移動リクエストを提出します。ただし、寮の席が空いたままになることは許されず、移動を希望する学生の代わりに別の学生がその部屋に入ってくれる場合にのみ、移動リクエストが受理されます。そこで本記事では、与えられたリクエストの中から、実際に同時に満たすことのできるリクエストの最大数を求める方法を解説します。

例えば、入力が n = 3、requests = [[0,2],[1,0],[2,1]] の場合、出力は 3 になります。これは次のように3件すべての移動が成立するためです。

• 部屋0の学生が部屋2へ移動する
• 部屋1の学生が部屋0へ移動する
• 部屋2の学生が部屋1へ移動する

解決のアプローチ

この問題は、リクエストの部分集合をすべて試す「組み合わせ全探索」で解くことができます。ある集合のリクエストがすべて同時に成立するためには、各部屋について「出ていく人数」と「入ってくる人数」が一致していなければなりません。具体的な手順は以下の通りです。

• k をリクエスト総数から1まで1ずつ減らしながらループする
• リクエストの中から k 個を選ぶすべての組み合わせについて調べる
• サイズ n の配列 d を用意し、すべての要素を0で初期化する
• 選ばれた各リクエスト i について、出発元の部屋のカウントを1減らし、移動先の部屋のカウントを1増やす
• d のすべての要素が0(空席も過剰な入居も発生していない状態)であれば、その k が答えなので返す

どの組み合わせでも条件を満たせなかった場合は 0 を返します。計算量はリクエスト数を m とすると O(2^m × m) となり指数オーダーですが、リクエスト数が少ない場合は十分実用的です。

実装例

理解を深めるために、Pythonでの実装を見てみましょう。

from itertools import combinations

def solve(n, requests):
    for k in range(len(requests), 0, -1):
        for c in combinations(range(len(requests)), k):
            d = [0] * n
            for i in c:
                d[requests[i][0]] -= 1
                d[requests[i][1]] += 1
            if not any(d):
                return k
    return 0

print(solve(3, [[0,2],[1,0],[2,1]]))

入力

3, [[0,2],[1,0],[2,1]]

出力

3

このコードでは、itertools.combinations を使って選択するリクエストの組み合わせを列挙し、大きい k から順に検証することで、最初に見つかった成立する組み合わせのサイズが最大値になります。配列 d の要素がすべて0であることを any 関数の否定で判定している点がポイントです。