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)))
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- How to interpret those 2 lambdas properly? An explanation in detail is welcome.
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?
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?
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))
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)))
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))
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))
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))