在 PAIP 中了解 Peter Norvig 的置换解决方案 [英] Understanding Peter Norvig's permutation solution in PAIP
问题描述
Peter Norvig 的 PAIP 书籍包含此代码作为置换问题的解决方案(为简洁起见，删除了某些部分)
Peter Norvig's PAIP book contains this code as a solution to the permutation problem (some sections are removed for brevity)
(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 的部分确实很棒，但有点难以理解，因为有许多相互混合的移动部分.我的问题是:
The part where 2 lambdas are involved is indeed brilliant yet a bit hard to comprehend as there are many moving parts intermingled into each other. My questions are:
1- 如何正确解释这 2 个 lambda?欢迎详细解释.
1- How to interpret those 2 lambdas properly? An explanation in detail is welcome.
2- Norvig 如何正确推断第一个地图函数应该是 mapcan?
2- How did Norvig rightly infer that the first map function should be mapcan?
可选:他最初是如何想到这么短而有效的解决方案的?
Optional: How did he in general think of such a short yet effective solution in the first place?
推荐答案
几乎可以肯定 Norvig 的想法反映在代码注释中.编写递归函数定义的主要原因之一是避免考虑计算的细节.编写递归定义可以让你专注于你想要做的事情的更高层次的描述:
Almost certainly Norvig's thinking is reflected in the code comments. One of the main reasons for writing a recursive function definition is to avoid thinking about the details of the calculation. Writing recursive definitions allows you to focus on higher-level descriptions of what you want to do:
如果你想找到一个包元素的所有排列，从包中取出第一个元素，找到剩余元素的所有排列，然后将被删除的元素添加到这些排列的前面.然后从包中取出第二个元素，找到剩余元素的所有排列，并将删除的元素添加到这些排列的前面.继续直到您从包中取出每个元素并收集列表中的所有排列.
If you want to find all permutations of a bag of elements, remove the first element from the bag, find all permutations of the remaining elements, and add the removed element to the front of those permutations. Then remove the second element from the bag, find all permutations of the remaining elements, and add the removed element to the front of those permutations. Continue until you have removed each element from the bag and collect all of the permutations in a list.
这是一个非常简单的描述，说明如何生成元素包的所有排列.如何将其转换为代码?
This is a pretty straightforward description of how you can generate all permutations of a bag of elements. How to convert that into code?
我们可以在包上映射一个函数，对于包的每个元素 e，返回一个包含除 e 之外的所有元素的列表，从而得到一个列表列表:
We can map a function over the bag that, for each element e of the bag, returns a list containing all but e, resulting in a list of lists:
CL-USER> (let ((bag '(a b c)))
(mapcar #'(lambda (e) (remove e bag)) bag))
((B C) (A C) (A B))
但是，对于每个子集，我们要生成一个排列列表，并且我们希望将 e 放在每个排列的前面.我还没有定义 permutations，所以我将使用 list 作为替代(一个排列列表就是一个列表列表):
But, for each one of the subsets we want to generate a list of permutations, and we want to cons e onto the front of each permutation. I haven't defined permutations yet, so I will use list as a substitute (a list of permutations is a list of lists):
CL-USER> (let ((bag '(a b c)))
(mapcar #'(lambda (e)
(mapcar #'(lambda (p) (cons e p))
(list (remove e bag))))
bag))
(((A B C)) ((B A C)) ((C A B)))
内部 mapcar 接受一个排列列表(目前只有一个排列)并在每个排列的前面添加 e.外部 mapcar 为包中的每个元素迭代这个过程，将结果放入一个列表中.但是，由于内部 mapcar 的结果是一个排列列表，所以外部 mapcar 的合并结果是一个排列列表的列表.此处可以使用 mapcan 代替 mapcar 来附加映射结果.也就是说，我们真的想将内部 mapcar 创建的排列列表附加在一起:
The inner mapcar takes a list of permutations (only one permutation at the moment) and adds e to the front of each permutation. The outer mapcar iterates this process for each element in the bag, consing the results into a list. But, since the result of the inner mapcar is a list of permutations, the consed together results of the outer mapcar is a list of lists of permutations. Instead of mapcar, mapcan can be used here to append the results of mapping. That is, we really want to append the lists of permutations created by the inner mapcar together:
CL-USER> (let ((bag '(a b c)))
(mapcan #'(lambda (e)
(mapcar #'(lambda (p) (cons e p))
(list (remove e bag))))
bag))
((A B C) (B A C) (C A B))
现在我们有一个排列列表，每个元素表示在第一个位置，但我们需要获得其余的排列.我们需要将元素 e 从包中 cons 到一个列表，而不是将包中的元素 ee 之后包的每个排列都被删除了.为此，我们需要继续定义permutations，并且需要实现一个基本情况:当包为空时，置换列表包含一个空包:
Now we have a list of permutations with each element represented in the first position, but we need to get the rest of the permutations. Instead of consing the elements e from the bag to a list that is only the bag with e removed, we need to cons the elements e to each permutation of the bag after e has been removed. To do this we need to go ahead and define permutations, and we need to implement a base case: when the bag is empty, the list of permutations contains an empty bag:
CL-USER> (defun permutations (bag)
(if (null bag)
'(())
(mapcan #'(lambda (e)
(mapcar #'(lambda (p) (cons e p))
(permutations (remove e bag))))
bag)))
PERMUTATIONS
CL-USER> (permutations '(a b c))
((A B C) (A C B) (B A C) (B C A) (C A B) (C B A))
现在我们完成了；包中的每个元素 e 都被放置在包其余部分的每个排列的前面.添加对 print 的调用可能有助于使事件序列更加清晰:
Now we are done; each element e from the bag has been consed onto the front of every permutation of the rest of the bag. Adding a call to print might help make the sequence of events more clear:
CL-USER> (defun permutations (bag)
(if (null bag)
'(())
(mapcan #'(lambda (e)
(let ((perms (mapcar #'(lambda (p) (cons e p))
(permutations (remove e bag)))))
(print perms)
perms))
bag)))
PERMUTATIONS
CL-USER> (permutations '(a b c))
((C))
((B C))
((B))
((C B))
((A B C) (A C B))
((C))
((A C))
((A))
((C A))
((B A C) (B C A))
((B))
((A B))
((A))
((B A))
((C A B) (C B A))
((A B C) (A C B) (B A C) (B C A) (C A B) (C B A))
这篇关于在 PAIP 中了解 Peter Norvig 的置换解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
