14

Pythonでの再帰について学び、割り当てを完了しました。そのうちの1つは、任意にネストされたリストのリスト内のすべての要素をカウントすることでした。このサイトを検索しましたが、見つかった回答はすべて再帰呼び出しを使用しているようです。再帰的に表現できるものはすべて反復的に表現でき、Pythonでは反復が好ましいと教えられてきたので、Python 2.6で再帰またはインポートされたモジュールなしで（学習演習として）これをどのように達成しますか？（ネストされたリスト自体は、その内容と同様に要素としてカウントされます。）例：

>>> def element_count(p):
...     count = 0
...     for entry in p:
...         count += 1
...         if isinstance(entry, list):            
...             count += element_count(entry)
...     return count
>>> print element_count([1, [], 3]) 
3 
>>> print element_count([1, [1, 2, [3, 4]]])
7
>>> print element_count([[[[[[[[1, 2, 3]]]]]]]])
10

これは反復を使用してどのように記述されますか？

4

3 に答える 3

17

これを行う1つの方法は次のとおりです。

def element_count(p):
  q = p[:]
  count = 0
  while q:
    entry = q.pop()
    if isinstance(entry, list):
      q += entry
    count += 1
  return count

print element_count([1, [], 3]) 
print element_count([1, [1, 2, [3, 4]]])
print element_count([[[[[[[[1, 2, 3]]]]]]]])

このコードは、調べる対象のキューを維持します。ループがサブリストに遭遇するたびに、その内容をキューに追加します。

于 2012-05-14T14:07:03.403 に答える
10

通常、各再帰問題は、スタックを使用して反復問題に変換できます。この場合は次のようになりlistます。

def element_count(p):
    elements = list(p)
    count = 0
    while elements:
        entry = elements.pop()
        count += 1
        if isinstance(entry, list):
            elements.extend(entry)
    return count
于 2012-05-14T14:12:13.823 に答える
2

このバージョンの はelement_count、他のバージョンよりもいくらか強力であることに気付くかもしれません。反復をサポートするすべてのコンテナーを処理でき、再帰コンテナーを無限の要素を持つものとして正しく識別します。

>>> def element_count(p):
    stack, pointers, count = [iter(p)], set([id(p)]), 0
    while stack:
        for item in stack.pop():
            try:
                iterator = iter(item)
            except TypeError:
                pass
            else:
                location = id(item)
                if location in pointers:
                    return float('inf')
                stack.append(iterator)
                pointers.add(location)
            count += 1
    return count

>>> element_count([1, [], 3])
3
>>> element_count([1, [1, 2, [3, 4]]])
7
>>> element_count([[[[[[[[1, 2, 3]]]]]]]])
10
>>> p = [1, 2, 3]
>>> element_count(p)
3
>>> p.append({4, 5, 6})
>>> element_count(p)
7
>>> p.append(p)
>>> element_count(p)
inf
>>>
于 2012-05-14T14:48:42.453 に答える