帮助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解决方案在结构上有所不同。

如果您遇到困难时，只需更新您的问题，无论您所做的任何进展以及您设法拼凑的任何代码。