Tìm danh sách lồng nhau nhất bên trong danh sách trong Common Lisp

Question

Tôi mới dùng Common Lisp và lập trình hàm, nhưng tôi có nhiều kinh nghiệm về ngôn ngữ như C, C++, C#, Java và vân vân. Tôi gặp sự cố khi tìm danh sách lồng nhau nhất bên trong danh sách. đầu vào của tôi là một cái gì đó như thế này:

(0 1 (2 3) 4 (5 (6 (7) 8)) 9) 

Tôi muốn có được danh sách lồng nhau nhất trong danh sách này mà trong trường hợp này là

(7) 

tôi đã có một ý tưởng mà tôi có thể san bằng danh sách bằng cách nào đó , cho đến khi chỉ còn lại một danh sách phụ. Để minh họa cho những gì tôi muốn nói, đây là một vài bước sau:

Bước 1. - đầu vào:

(0 1 (2 3) 4 (5 (6 (7) 8)) 9) 

Bước 2. - flatten vào "mức độ đầu tiên":

(0 1 2 3 4 5 (6 (7) 8) 9) 

Bước 3. - flatten trên "cấp thứ hai":

(0 1 2 3 4 5 6 (7) 8 9) 

Bây giờ chỉ còn lại một danh sách lồng nhau, có nghĩa là danh sách lồng nhau nhất. Nhưng tôi thấy một vấn đề ở đây, khi hai hoặc nhiều danh sách như vậy sẽ xảy ra. Hãy chia sẻ suy nghĩ của bạn về điều này.

Tôi đang gặp sự cố khi đưa quy trình này vào thực tế trong Common Lisp, vì vậy tôi sẽ biết ơn đối với một số gợi ý đúng hướng, có thể một số mã mẫu và v.v. Đây là một bài tập về nhà, vì vậy tôi không thực sự mong đợi một giải pháp đầy đủ, nhưng sẽ rất vui nếu ai đó chỉ ra một giải pháp dễ dàng hơn và tốt hơn và thực hiện nó.

Answer 1

Đây là của tôi (không phải là rất sạch sẽ) giải pháp trong CL:

(defun deepest-list (lst) 
    (let ((max-depth 0) ret) 
    (labels ((inner-deepest-lst (lst depth) 
      (cond 
     ((null lst) depth) 
     ((listp (car lst)) 
      (let ((local-max (max 
        (inner-deepest-lst (first lst) (1+ depth)) 
        (inner-deepest-lst (rest lst) (1+ depth))))) 
      (and (> local-max max-depth) (setf ret (first lst) max-depth local-max)) 
      local-max)) 
     (t (inner-deepest-lst (rest lst) depth))))) 
     (inner-deepest-lst lst 1)) 
    ret)) 

chỉnh sửa:

Sau một ý nghĩ thứ hai, đây là một giải pháp nhẹ sạch:

(defun deepest-list (lst) 
    (labels ((dl (lst depth) 
     (cond 
      ((atom lst) (cons 0 lst)) 
      ((every #'atom lst) (cons depth lst)) 
      (t (funcall (lambda (x y) (if (> (car x) (car y)) x y)) 
       (dl (car lst) (1+ depth)) 
       (dl (cdr lst) depth)))))) 
    (rest (dl lst 0)))) 

Answer 2

Cách tiếp cận làm phẳng danh sách lặp lại của bạn có thể hoạt động tốt, mặc dù đây không phải là cách thanh lịch hiệu quả nhất (chủ quan) để thực hiện.

Nếu có nhiều hơn một danh sách như vậy, đầu ra chính xác sẽ phụ thuộc vào đặc điểm kỹ thuật - bạn có nên trả lại tất cả chúng hay chỉ đầu tiên hoặc ném lỗi?

Nếu tôi là bạn, tôi sẽ xem xét để đưa ra một hàm đệ quy để giải quyết vấn đề. Mỗi cấp độ đệ quy về cơ bản sẽ xử lý các yếu tố của một cấp độ nhất định của các danh sách lồng nhau. Hãy suy nghĩ về những gì mỗi cuộc gọi đệ quy nên làm - nó rất đơn giản nếu một khi nó nhấp chuột!

Answer 3

Đây là giải pháp của tôi, sử dụng cách tiếp cận tương tự với OP. (Trong trường hợp nhiều mục sâu nhất, tất cả chúng đều được trả lại.)

Tôi đã viết nó trong Đề án, có thể sẽ không được dịch ngay lập tức sang Common Lisp, vì vậy tôi không cảm thấy rằng nó sẽ hoàn thành giveaway. Tuy nhiên, nó có tiềm năng để được spoilery, do đó, tread thận trọng.

(define (deepest lst) 
    (let ((filtered (filter pair? lst))) 
    (cond ((null? filtered) lst) 
      (else (deepest (concatenate filtered))))))