Pythonでネストされたリストをフラット化するイテレータの実装方法

整数が入れ子になったリスト（ネストされたリスト）があるとします。このリストを平坦化（フラット化）するためのイテレータを実装する必要があります。各要素は整数、またはリストのいずれかであり、そのリストの要素もまた整数や別のリストである可能性があります。

例えば、入力が [[1, 1], 2, [1, 1]] の場合、出力は [1, 1, 2, 1, 1] のようになります。

解決のアプローチ

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

• 初期化処理： コンストラクタでネストされたリストを受け取り、結果を格納するための空のリスト res とインデックス index = 0 を用意し、再帰関数 getVal() を呼び出します。
• getVal() メソッド： ネストされたリストを受け取り、その要素を順番に走査します。要素が整数であれば res リストに追加し、リストであれば自分自身を再帰的に呼び出してさらに展開します。
• next() メソッド： 現在のインデックスが指す値を返し、インデックスを1つ進めます。
• hasNext() メソッド： 次に返すべき要素が存在する場合は True を、存在しない場合は False を返します。

Pythonでの実装例

以下の実装を見ると、より理解しやすくなります。

class NestedIterator(object):
    def __init__(self, nestedList):
        self.res = []
        self.index = 0
        self.getVal(nestedList)
        #print(self.res)
    def getVal(self,NestedList):
        for item in NestedList:
            if isinstance(item, int):
                self.res.append(item)
            else:
                self.getVal(item)
    def next(self):
        self.index+=1
        return self.res[self.index-1]
    def hasNext(self):
        if self.index == len(self.res):
            return False
        return True
ob = NestedIterator([[1,1],2,[1,1]])
while ob.hasNext():
    print(ob.next())

入力

[[1,1],2,[1,1]]

出力

1
1
2
1
1

実装のポイント

このアプローチでは、isinstance() 関数を使って要素が整数かどうかを判定しています。整数であればそのまま結果リストに追加し、リスト型であれば再帰的に処理を続けることで、どれだけ深くネストされた構造でも正しくフラット化できます。

なお、この方法は初期化時にすべての要素を展開してしまうため、データ量が非常に大きい場合にはメモリ使用量に注意が必要です。そのようなケースでは、ジェネレータやスタックを使った遅延評価方式の実装も検討するとよいでしょう。