Pythonでリスト内のすべての部分リストに一意な要素が含まれているかをチェックするプログラム

要素を格納したリスト nums が与えられ、そのすべての部分リスト(サブリスト)について「その部分リスト内でちょうど1回だけ出現する要素が少なくとも1つ存在するか」を判定する問題を考えます。この問題は線形時間で解くことが求められます。

たとえば、入力が nums = [5, 10, 20, 10, 0] の場合、出力は True になります。これは、[[5], [10], [20], [10], [0], [5,10], [10,20], [20,10], [10,0], [5,10,20], [10,20,10], [20,10,0], [5,10,20,10], [10,20,10,0], [5,10,20,10,0]] のように生成されるすべての部分リストに、出現頻度が1の要素が必ず含まれているためです。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• has_unique() 関数を定義します。この関数は left と right を引数に取ります。
• left >= right の場合は True を返します(範囲が空または要素数1なら条件は自明に満たされます)。
• counts:nums[left] から nums[right] までに含まれる各要素の出現回数を記録した辞書を作成します。
• counts の最小値が 1 より大きい場合(= すべての要素が2回以上出現している場合)は False を返します。
• start := left と初期化します。
• index を left から right までループさせます。
  • counts[nums[index]] == 1(その要素が一意である)の場合:
    • has_unique(start, index - 1) が False であれば False を返します。
    • start := index + 1 と更新します。
• 最後に has_unique(start, right) を返します。
• メイン処理からは has_unique(0, len(nums) - 1) を呼び出して結果を返します。

このアルゴリズムのポイントは、一意な要素(1回だけ出現する要素)を境界として区間を分割し、それぞれの小区間に対して再帰的に同じ判定を行う点です。ある区間内に一意な要素がひとつも存在しなければ、その区間は条件を満たさないため False となります。

実装例

以下の実装を見ると、理解がより深まるでしょう。

from collections import Counter
def solve(nums):
   def has_unique(left, right):
      if left >= right:
         return True

      counts = Counter(nums[left : right + 1])
      if min(counts.values()) > 1:
         return False

      start = left

      for index in range(left, right + 1):
         if counts[nums[index]] == 1:
            if not has_unique(start, index - 1):
               return False
            start = index + 1

      return has_unique(start, right)

   return has_unique(0, len(nums) - 1)

nums = [5, 10, 20, 10, 0]
print(solve(nums))

入力

[5, 10, 20, 10, 0]

出力

True