Policz wszystkie elementy na liście arbitralnie zagnieżdżonej listy bez rekurencji

Question

Właśnie dowiedziałem się o rekursji w Pythonie i ukończyłem zadania, z których jednym było zliczanie wszystkich elementów na liście dowolnie zagnieżdżonych list. Przeszukałem tę stronę, a wszystkie znalezione odpowiedzi wydają się korzystać z wywołań rekursywnych. Ponieważ nauczono go, że wszystko, co może być wyrażone rekurencyjnie, może być wyrażane iteracyjnie, a w Pythonie preferowane jest iterowanie, w jaki sposób można to osiągnąć bez rekursji lub importowanych modułów w Pythonie 2.6 (jako ćwiczenie uczenia się)? (Lista zagnieżdżona sama będzie traktowany jako element, podobnie jak jego zawartość). Na przykład:

>>> 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 

Jak miałoby to być napisane przy użyciu iteracji?

Answer 1

Oto jeden ze sposobów, aby to zrobić:

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]]]]]]]]) 

Kod utrzymuje kolejkę rzeczy należy spojrzeć. Ilekroć pętla napotyka podlistę, dodaje jej zawartość do kolejki.

Answer 2

Zazwyczaj każdy rekurencyjny problem może być zamienione na iteracyjny jakoś za pomocą stosu, w tym przypadku 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 

Answer 3

Można znaleźć tej wersji element_count się być nieco bardziej wydajne niż inne. Może obsłużyć wszystkie pojemniki obsługujące iterację i poprawnie identyfikuje rekurencyjne pojemniki jako mające nieskończoną liczbę elementów.

>>> 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 
>>>