Pythonで再帰的インデックス参照を用いて要素の集合のサイズを求めるプログラム

問題の概要

数字のリスト A と別の数値 k が与えられたとします。このとき、{A[k], A[A[k]], A[A[A[k]]], ...} のような新しい集合を作成します。インデックスが範囲外になる直前まで処理を続けます。最終的に、この集合のサイズを求めます。ただし、途中で循環（サイクル）が発生した場合は -1 を返します。

たとえば、入力が A = [1,2,3,4,5,6,7]、k = 1 である場合、A[1] = 2、A[2] = 3、A[3] = 4、A[4] = 5、A[5] = 6、A[6] = 7 となるため、集合は {2,3,4,5,6,7} となり、そのサイズは 6 です。

解決手順

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

• 空の集合 seen を用意します
• k がリスト A の長さ未満である間、次の処理を繰り返します
  • A[k] がすでに seen に含まれている場合は、循環が発生しているため -1 を返します
• A[k] を seen に追加します

• k を A[k] に更新します

• ループ終了後、seen のサイズを返します

実装例

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

サンプルコード

class Solution:
   def solve(self, A, k):
      seen = set()
      while k < len(A):
         if A[k] in seen:
            return -1
         seen.add(A[k])
         k = A[k]
      return len(seen)
ob = Solution()
print(ob.solve([1,2,3,4,5,6,7], 1))

入力

[1,2,3,4,5,6,7], 1

出力

6

アルゴリズムのポイント

このアルゴリズムの核心は、訪問済みの要素を記録する集合を使う点です。再帰的なインデックス参照では、同じ値を二度参照すると必ず無限ループ（循環）に陥ります。そこで、各ステップで参照した値を set 型の変数 seen に追加し、既存の値と重複した時点で即座に -1 を返すことで、効率的に循環を検出できます。

計算量については、リストの各要素は最大一度しか参照されないため、時間計算量は O(n)、使用する記憶領域も最大 n 個の要素を格納するため O(n) となります。ここで n はリスト A の長さです。