了解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-如何正确解释这两个lambda?欢迎进行详细说明.
1- How to interpret those 2 lambdas properly? An explanation in detail is welcome.
2-诺维格如何正确推断第一个地图函数应为 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 限制在每个排列的前面.我尚未定义置换，所以我将使用 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 .外部的
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 限制在仅删除了 e 的包的列表之外，我们需要将元素 e 限制为删除 e 之后，袋子的每个排列.为此，我们需要继续定义 permutations ，我们需要实现一个基本情况:当bag为空时，排列列表包含一个空bag:
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屋！
