Conta tutti gli elementi nell'elenco di elenchi nidificati arbitrari senza ricorsione

Question

Ho appena saputo della ricorsione in Python e ho completato i compiti, uno dei quali era contare tutti gli elementi in un elenco di liste arbitrariamente annidate. Ho cercato questo sito e le risposte trovate sembrano utilizzare tutte le chiamate ricorsive. Poiché è stato insegnato che tutto ciò che potrebbe essere espresso in modo ricorsivo potrebbe essere espresso in modo iterativo, e l'iterazione è preferibile in Python, come sarebbe possibile farlo senza ricorsione o moduli importati in Python 2.6 (come esercizio di apprendimento)? (Una lista annidata stessa sarebbe essere considerato come un elemento, come farebbe il suo contenuto.) Ad esempio:

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

Come potrebbe questo essere scritta utilizzando l'iterazione?

Answer 1

Ecco un modo per farlo:

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

Il codice mantiene una coda di cose da guardare. Ogni volta che il ciclo incontra un sottoelenco, aggiunge il suo contenuto alla coda.

Answer 2

Di solito ogni problema ricorsiva può essere convertito in un qualche modo iterativo utilizzando uno stack, in questo caso un 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

Si potrebbe trovare questa versione di element_count essere un po 'più potente rispetto agli altri. Può gestire tutti i contenitori che supportano l'iterazione e identifica correttamente i contenitori ricorsivi come aventi un numero infinito di elementi.

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