Python Đệ quy qua các đồ vật và các đối tượng trẻ em, số sâu In con

Question

Tôi có một lớp đơn giản với một thuộc tính có thể chứa một danh sách các đối tượng của cùng một lớp

class BoxItem: 
    def __init__(self, name, **kw): 
     self.name = name 
     self.boxItems = [] 
     ... #more attributes here 

box1 = BoxItem('Normal Box') 
box2 = BoxItem('Friendly Box') 
box3 = BoxItem('Cool Box') 
box4 = BoxItem('Big Box', [box1, box2]) #contains some children 
example = BoxItem('Example Box', [box4,box3]) #contains another level of children 

Làm việc với 'dụ' đối tượng hộp của chúng tôi, tôi muốn cơ động thông qua chiều sâu của tất cả trẻ em hộp có thể nó có thể có, và in ra các đối tượng được định dạng như sau:

1 Example Box 
1.1 Big Box 
    1.1.1 Normal Box 
    1.1.2 Friendly Box 
1.2 Cool Box 

tabbing giữa là không cần thiết, chỉ muốn hiển thị các định dạng cây rõ ràng. Tôi có thể tự mình đi xuống các đối tượng và in ra các tiêu đề của họ, nhưng tôi không thể in ra các số trước cho thấy mối quan hệ cha/con. (1, 1.1, 1.2 ...)

Cảm ơn trước sự giúp đỡ của bạn :)

Sửa Dưới đây là những gì tôi đã làm việc với rất xa

def print_boxes(box_list): 
    node_count = 0 
    for box in box_list: 
    node_count += 1 
    print str(node_count)+' '+box.name #prints out the root box 
    recursive_search(box,node_count) 

def recursive_search(box,node_count): #recursive automatically 
    level = 0 
    for child in box.boxItems: 
    level += 1 
    for x in range(len(child.boxItems)): 
     print x+1 #this prints out some proper numbers 
    print "level: "+str(level) #experiment with level 
    print child.name #prints out child box name 
    recursive_search(child,node_count) #runs the function again inside the function 

Answer 1

Tôi nghĩ rằng nó có thể hữu ích hơn cho bạn nếu tôi đăng một ví dụ làm việc về cách thực hiện điều này, trái ngược với việc đi qua nơi bạn viết mã đang gặp sự cố. Chúng ta có thể hiểu được nhanh hơn rất nhiều theo cách đó. Mã của bạn có ý tưởng chính xác rằng nó cần phải theo dõi độ sâu khi nó đi. Nhưng điều duy nhất nó thiếu là một cảm giác chiều sâu lồng nhau (cây). Nó chỉ biết trước node_count, và sau đó đếm con hiện tại của nó.

Ví dụ của tôi sử dụng dấu đóng để khởi động đối tượng theo dõi độ sâu, sau đó tạo hàm bên trong để thực hiện phần đệ quy.

def recurse(box): 

    boxes = not isinstance(box, (list, tuple)) and [box] or box 

    depth = [1] 

    def wrapped(box): 

     depthStr = '.'.join([str(i) for i in depth]) 
     print "%s %s" % (depthStr, box.name) 

     depth.append(1) 
     for child in box.boxItems: 
      wrapped(child) 
      depth[-1] += 1 
     depth.pop() 

    for box in boxes: 
     wrapped(box) 
     depth[0] += 1 

Mẫu đầu ra từ ví dụ của bạn:

>>> recurse(example) 
1 Example Box 
1.1 Big Box 
1.1.1 Normal Box 
1.1.2 Friendly Box 
1.2 Cool Box 

>>> recurse([example, example]) 
1 Example Box 
1.1 Big Box 
1.1.1 Normal Box 
1.1.2 Friendly Box 
1.2 Cool Box 
2 Example Box 
2.1 Big Box 
2.1.1 Normal Box 
2.1.2 Friendly Box 
2.2 Cool Box 

Breaking này xuống:

Đầu tiên chúng ta chấp nhận một đối số hộp, và tự động chuyển đổi nó tại địa phương vào một danh sách, nếu bạn chỉ có được chuyển vào một mục hộp duy nhất. Bằng cách đó bạn có thể vượt qua một trong hai đối tượng hộp, hoặc một danh sách/tuple của họ.

depth là trình theo dõi độ sâu của chúng tôi. Đó là một danh sách các int mà chúng ta sẽ xây dựng và co lại khi đệ quy xảy ra. Nó bắt đầu từ 1 cho hạng mục đầu tiên/cấp độ đầu tiên. Theo thời gian, nó có thể trông giống như sau: [1,1,2,3,1] tùy thuộc vào độ sâu của nó. Đây là sự khác biệt lớn giữa mã của tôi và của bạn. Mỗi đệ quy có quyền truy cập vào trạng thái này.

Bây giờ chúng tôi có hàm bên trong là wrapped. Nó sẽ lấy một mục hộp hiện tại và in nó, và sau đó lặp lại trên con của nó.Chúng tôi nhận được chuỗi in của chúng tôi bằng cách tham gia danh sách độ sâu hiện tại và sau đó là tên.

Mỗi khi chúng ta rơi vào danh sách trẻ em, chúng ta thêm một cấp độ bắt đầu 1 vào danh sách chiều sâu của chúng ta, và khi chúng ta thoát khỏi vòng lặp con đó, chúng ta bật nó trở lại. Đối với mỗi đứa trẻ trong vòng lặp đó, chúng tôi tăng mục cuối cùng lên.

Bên ngoài đó wrapped chức năng bên trong, sau đó chúng tôi bắt đầu toàn bộ điều bằng cách lặp qua các hộp ban đầu của chúng tôi, gọi wrapped và sau đó tăng cấp đầu tiên của chúng tôi.

Hàm bọc bên trong sử dụng danh sách độ sâu trong bao đóng. Tôi sẵn sàng đặt cược rằng những người khác có thể cung cấp một số cải tiến hơn nữa về điều này, nhưng những gì tôi đã đưa ra cho một ví dụ.

Lưu ý về args cho hàm

Chúng ta có thể cũng đã được thiết kế để recurse thay vì phải mất một danh sách đối số chiều dài thay đổi, thay vì kiểm tra cho một danh sách. Nó sẽ giống như thế này (và sẽ thoát khỏi đó boxes = kiểm tra đầu tiên):

def recurse(*boxes): 
    #boxes will always come in as a tuple no matter what 

>>> recurse(example) 
>>> recurse(example, example, example) 

Và nếu bạn ban đầu được bắt đầu với một danh sách các mục hộp, bạn có thể vượt qua nó bằng cách thực hiện:

>>> boxes = [example, example, example] 
>>> recurse(*example) # this will unpack your list into args 

Answer 2

Bạn có hai tùy chọn:

1. Theo dõi thông tin bổ sung dưới dạng tham số bổ sung trong đệ quy của bạn, ví dụ: myRecursiveFunction(..., ancestry=[])
2. Để mỗi BoxItem theo dõi cha mẹ của nó, bất cứ khi nào nó được nhúng trong một BoxItem (trong công cụ xây dựng __init__, đặt child.parent = self cho mỗi đứa trẻ). Điều này là xấu nếu bạn có kế hoạch để có một BoxItem trong nhiều hơn một hộp.