Đếm tất cả các phần tử trong danh sách danh sách lồng nhau tùy ý mà không đệ quy

Question

Tôi vừa học về đệ quy bằng Python và đã hoàn thành nhiệm vụ, một trong số đó là đếm tất cả các phần tử trong danh sách các danh sách lồng nhau tùy ý. Tôi đã tìm kiếm trang web này và các câu trả lời được tìm thấy tất cả dường như sử dụng các cuộc gọi đệ quy. Vì nó đã được dạy rằng bất cứ điều gì có thể được biểu diễn đệ quy có thể được biểu diễn lặp đi lặp lại, và lặp lại được ưa thích trong Python, làm thế nào điều này sẽ được thực hiện mà không đệ quy hoặc mô-đun được nhập trong Python 2.6 (như một bài tập học tập)? (Một danh sách lồng nhau tự sẽ được tính là một yếu tố, như sẽ nội dung của nó.) Ví dụ:

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

Làm thế nào điều này sẽ được viết bằng lặp?

Answer 1

Dưới đây là một cách để làm điều đó:

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

Mã duy trì một danh sách các điều cần được xem xét. Bất cứ khi nào vòng lặp gặp một danh sách con, nó sẽ thêm nội dung của nó vào hàng đợi.

Answer 2

Thông thường mỗi vấn đề đệ quy có thể được chuyển đổi sang một lặp đi lặp lại bằng cách nào đó bằng cách sử dụng một chồng, trong trường hợp này một 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

Bạn có thể tìm thấy phiên bản này của element_count được phần nào mạnh mẽ hơn những người khác. Nó có thể xử lý tất cả các thùng chứa hỗ trợ lặp lại, và nó xác định chính xác các thùng chứa đệ quy khi có một số lượng các phần tử vô hạn.

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