Pythonで配列から指定した部分配列を順番に切り出せるか判定するプログラム

2次元配列 groups と、別の1次元配列 nums が与えられているとします。このとき、nums から互いに重ならないn個の部分配列を選び出せるかどうかを判定します。条件として、i番目の部分配列は groups[i] と完全に一致すること、また i > 0 の場合は (i-1) 番目の部分配列が nums 内で i 番目より先に現れることが求められます。

例えば、入力が groups = [[2,-2,-2],[4,-3,0]]、nums = [1,-1,0,2,-2,-2,4,-3,0] の場合、出力は True になります。これは、groups[0] が nums のインデックス3〜5に、groups[1] がインデックス6〜8にそれぞれ存在し、順序の条件も満たしているためです。

解法のアプローチ

この問題は、貪欲法（グリーディ法）の考え方で解くことができます。手順は以下の通りです。

• 探索開始位置を表す変数 i を 0 で初期化します。
• groups の各要素 grp について、以下を繰り返します。
  • j を i から nums の末尾まで動かしながら、nums[j:j+len(grp)] が grp と一致するかを確認します。
  • 一致した場合、i を j + len(grp) に更新し、次のグループの探索へ進みます。
  • nums の範囲内で一致する部分配列が1つも見つからなかった場合、False を返します。
• すべてのグループが見つかったら、True を返します。

一度マッチした部分は次の探索の対象外となるため、部分配列同士が重なることはありません。計算量は、グループ数をG、nums の長さをN、グループの最大長をLとすると O(G × N × L) 程度になります。

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(groups, nums):
    i = 0
    for grp in groups:
        for j in range(i, len(nums)):
            if nums[j:j+len(grp)] == grp:
                i = j + len(grp)
                break
        else:
            return False
    return True

groups = [[2,-2,-2],[4,-3,0]]
nums = [1,-1,0,2,-2,-2,4,-3,0]
print(solve(groups, nums))

このコードのポイントは、内側の for ループに else 節を組み合わせている点です。Pythonでは、for ループが break されずに最後まで実行されると else ブロックが実行されます。これにより「一致する部分配列が1つも見つからなかった場合に False を返す」という処理を、フラグ変数なしで簡潔に記述できます。

入力

[[2,-2,-2],[4,-3,0]], [1,-1,0,2,-2,-2,4,-3,0]

出力

True