Pythonで配列の断片から元の配列を再構築できるか判定する方法

問題の概要

すべての要素が一意（ユニーク）である整数配列 nums と、複数の小さな配列を要素として持つ配列 pieces が与えられているとします。このとき、pieces 内の配列を任意の順序で連結することによって、元の配列 nums を再現できるかどうかを判定するのが本記事のテーマです。

重要な制約として、各断片（pieces[i]）内部の要素の順序を入れ替えることは許されません。断片はそのままの形で使う必要があります。

具体例

たとえば、次のような入力を考えてみましょう。

• nums = [5,1,12,36,2,47,6]
• pieces = [[2,47,6],[12,36],[1],[5]]

この場合、出力は True になります。なぜなら、[[5], [1], [12,36], [2,47,6]] の順序で断片を連結すれば、元の配列 nums が完全に再現できるからです。

解決のアプローチ

この問題は、以下の手順で解くことができます。

1. 結果を格納するための空リスト temp を用意します。
2. pieces 内の各断片 p について、次の処理を行います。
   • p[0]（断片の先頭要素）が nums に存在しない場合は False を返します。
   • 断片の長さを l とし、nums 内における p[0] のインデックスを indx として取得します。
   • nums[indx:indx+l]（該当位置から始まる部分配列）が断片 p と一致しない場合は False を返します。
   • 一致する場合は、断片 p を temp に追加します。
3. すべての断片を処理した後、temp の長さが nums の長さと等しければ True、そうでなければ False を返します。

このアルゴリズムのポイントは、各断片の先頭要素が nums 内のどこに位置するかを調べ、その位置から始まる部分配列が断片と完全に一致するかを確認する点にあります。すべての要素が一意であるため、先頭要素の位置特定は常に正確に行えます。

Pythonでの実装例

それでは、上記のロジックをPythonコードで実装してみましょう。

def solve(nums, pieces):
    temp = []
    for p in pieces:
        if p[0] not in nums:
            return False
        l = len(p)
        indx = nums.index(p[0])
        if nums[indx:indx+l] != p:
            return False
        else:
            temp.extend(p)
    if len(nums) == len(temp):
        return True
    else:
        return False

nums = [5,1,12,36,2,47,6]
pieces = [[2,47,6],[12,36],[1],[5]]
print(solve(nums, pieces))

入力

[5,1,12,36,2,47,6], [[2,47,6],[12,36],[1],[5]]

出力

True

計算量について

この解法の計算量を見てみましょう。nums.index() の呼び出しには O(n) の時間がかかるため、全体の時間計算量は O(n × m) となります（n は nums の長さ、m は断片の数）。空間計算量については、temp リストの分だけ余分にメモリを使用します。

もしパフォーマンスをさらに重視する場合は、nums の各要素とそのインデックスを事前に辞書（ハッシュマップ）に登録しておくことで、位置検索を O(1) に高速化できます。要素数が多いデータセットを扱う際には、この最適化を検討するとよいでしょう。

まとめ

本記事では、配列の断片を任意の順序で連結して元の配列を再構築できるかどうかを判定するPythonプログラムを紹介しました。核心となる考え方は、「各断片の先頭要素の位置を nums 内で特定し、そこからの部分配列が断片と一致するかを検証する」というシンプルなものです。配列操作やスライスの理解を深めるのに役立つ、実践的な練習問題と言えるでしょう。