幫助Lisp代碼爲二叉樹

Question

我

(setq l2 '(1 (2 b (c 1 b))(a (1 2) d))) 

(defun drumuri (l3) 
    (cond ((atom l3) (cons l3 nil)) 
    (t (append 
      (cons (car l3) nil) 
      (drumuri (cadr l3)) 
      (cons (car l3) nil) 
      (drumuri (caddr l3)))))) 

(drumuri l2) 

，這讓我：

Break 2 
[4]>  DRUMURI 
Break 2 
[4]>  (1 2 B 2 C 1 C B 1 A 1 2 1 NIL A D) 

，但我需要：

((1 2 B)(1 2 C 1)(1 2 C B)(1 A 1 2)(1 A D)) 

好了好消息，我發現了一些答案：

(setq l2 '(1 (2 b (c 1 b))(a (1 2) d))) 
(defun drumuri (l3) 
(cond ((atom l3) (cons l3 nil)) 
     (t (append (cons (car l3) nil) 
      (drumuri (cadr l3)))))) 
      (drumuri l2) 

和答案是：

[1]> 
(1 (2 B (C 1 B)) (A (1 2) D)) 
[2]> 
DRUMURI 
[3]> 
(1 2 B) 

接下來是第二個答案：

(defun drumuri (l4) 
    (cond ((atom l4)(cons l4 nil)) 
    (t (append (cons (car l4)nil) 
     (drumuri (caddr l4)))))) 
      (drumuri l2) 

和這個問題的答案是：

[1]> 
(1 (2 B (C 1 B)) (A (1 2) D)) 
[2]> 
DRUMURI 
[3]> 
(1 A D) 

所以所有剩下的就是找到：

（1 2 C 1）（1 2 CB）（1 A 1 2）

Answer 1

棘手的問題。不是特別複雜，但有一些挑剔的邊緣。由於這顯然是家庭作業，我會盡力幫助你，但同時也要避免給你餵食（並可能在這些目標中的一個或兩個都失敗）。所以我用Python編寫了它。希望這與Lisp相去甚遠，你仍然需要爲自己做一些好的思考。

>>> import operator 
>>> def drumuri(a): 
...  if isinstance(a, list): 
...   return reduce(operator.add, 
...      [[a[:1] + d for d in drumuri(x)] for x in a[1:]]) 
...  else: 
...   return [[a]] 
... 
>>> drumuri([1, [2, 'b', ['c', 1, 'b']], ['a', [1, 2], 'd']]) 
[[1, 2, 'b'], [1, 2, 'c', 1], [1, 2, 'c', 'b'], [1, 'a', 1, 2], [1, 'a', 'd']] 
>>> 

下面是從你的Lisp版本缺少的關鍵洞察力。因爲drumuri是遞歸的，所以每個級別都必須向其調用者返回相同類型的結構：路徑列表，其中每個路徑都是列表。總之，drumuri必須總是返回一個列表清單。你的葉子案例返回一個包含單個原子的列表。

你也在使用append時犯了一些錯誤，但是葉子問題可能會讓所有其他的東西變形。

編輯：讓我們看看是否可以幫助你發現你自己的解決方案。請按照下列步驟：

1. 編寫一個叫做prepend-to-paths功能，需要一個單頭和路徑列表，並返回與頭部添加到每個原始路徑前面的路徑列表。它應該如下：

   > (prepend-to-paths 1 '((2 B) (2 C 1) (2 C B) (A 1 2) (A D))) ;' 
   ((1 2 B) (1 2 C 1) (1 2 C B) (1 A 1 2) (1 A D)) 
   

2. 編寫一個叫做convert-to-paths函數，它未處理尾部元素的列表，並將它們轉換爲路徑。但是，它並不是完成所有工作，而是應該只考慮將輸入映射到路徑列表（依賴尚未寫入的drumuri來映射每個元素），然後將返回的路徑列表連接到單個列表中路徑。輸出（一次drumuri存在）應該是像這樣：

   > (convert-to-paths '((2 b (c 1 b)) (a (1 2) d))) ;' 
   ((2 B) (2 C 1) (2 C B) (A 1 2) (A D)) 
   

3. 寫drumuri功能。它應該使用cond按你原來的，但它返回原子作爲路徑列表中的表達式替換葉案：

   > (drumuri 'b) ;' 
   ((b)) 
   

   然後使用你寫的功能，在前面的步驟中的代碼替換(append ...)轉換輸入列表的頭部和尾部輸入路徑列表。

4. 一旦這三個函數很好地協同工作，您可以嘗試弄清楚如何將前兩個函數摺疊到drumuri的正文中。請注意，這樣做的最終結果可能與我給出的Python解決方案在結構上有所不同。

如果您遇到困難時，只需更新您的問題，無論您所做的任何進展以及您設法拼湊的任何代碼。