recursion - 了解 Peter Norvig 在 PAIP 中的置换解决方案

Question

Peter Norvig 的 PAIP 书籍包含此 code作为排列问题的解决方案(为简洁起见，删除了某些部分)

(defun permutations (bag)
  ;; If the input is nil, there is only one permutation:
  ;; nil itself
  (if (null bag)
      '(())
      ;; Otherwise, take an element, e, out of the bag.
      ;; Generate all permutations of the remaining elements,
      ;; And add e to the front of each of these.
      ;; Do this for all possible e to generate all permutations.
      (mapcan #'(lambda (e)
                  (mapcar #'(lambda (p) (cons e p))
                          (permutations (remove e bag))))
              bag)))

涉及 2 个 lambda 的部分确实很棒，但有点难以理解，因为有许多事件部分相互混合。我的问题是:

1-如何正确解释这 2 个 lambda？欢迎详细解释。

2- Norvig 如何正确推断出第一个映射函数应该是 mapcan ?

可选:他最初是如何想到这样一个简短而有效的解决方案的？

Answer 1

除了上面已经解释过的一些小区别之外，重要的是 mapcan和 mapcar是循环函数。所以双lambda可以简单地解释为循环中的循环。
您可以将其重写为

(dolist (e bag)
  (dolist (p (permutations (remove e bag)))
    (cons e p) ))

在这个骨架中，您仍然缺少如何累积结果。可以这样做，例如作为

(defun permutations (bag) 
  (if (null bag)  (list bag) 
    (let*  ((res (list 1))  (end res))
       (dolist  (e  bag  (cdr res))
           (dolist  (p  (permutations (remove e bag)))
               (rplacd  end  (list (cons e p)))
               (pop end))))))

mapcan 也是如此。和 mapcar ，更优雅，在 Norvig 的版本中。但我希望这个解释能让你更清楚。