Understanding Peter Norvig's permutation solution in PAIP

Question

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?

Answer 1

Apart from some small difference which has been explained above, the important thing is that mapcan and mapcar are loop functions. So the double lambda can be simply interpreted as a loop within a loop.

You could rewrite it as

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

In this skeleton you are still missing how to accumulate the results. It could be done e.g. as

(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))))))

The same is accomplished by mapcan and mapcar, much more elegantly, in Norvig's version. But I hope this explanation makes it more clear to you.

Answer 2

Concerning question 2 (on mapcan):

The Hyperspec says "mapcan..(is) like mapcar..except that the results of applying function are combined into a list by the use of nconc rather than list."

(mapcan #'identity '((1 2 3) (4 5 6))) ;=> (1 2 3 4 5 6)
(mapcar #'identity '((1 2 3) (4 5 6))) ;=> ((1 2 3) (4 5 6))

In the permutations function, if you had used mapcar instead of mapcan, you would have one more nesting layer for each of (permutations (remove e bag)), which would make the resulting list "grouped". To make this more clear, if you define a function permutations2, which is exactly the same with permutations, just using mapcar in place of mapcan:

(permutations '(1 2 3))  ;=> ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
(permutations2 '(1 2 3)) 
;=> (((1 (2 (3))) (1 (3 (2)))) ((2 (1 (3))) (2 (3 (1)))) ((3 (1 (2))) (3 (2 (1)))))

Therefore, the outer map function is mapcan, so that permutations returns a list of permutations (as the docstring says), and not a list of "groups" of permutations.

Concerning question 1 (on the lambdas):

In this case, the lambda-expressions look intermingled because they refer to variables defined outside of them, i.e. from the surrounding lexical environment (the first/outer refers to bag, the second/inner refers to e). In other words, to both mapcan and mapcar we are actually passing closures.

Since the code has the strategy described in its comments, we need:

1. To map over the elements of bag, which is what mapcan does here. So we need a function, that takes as argument an element (e) of bag and does something (the role of the outer lambda function).

2. To map over the permutations of the remaining elements, which is what mapcar does here. So we need a function, that takes as argument a permutation (p) of (permutations (remove e bag)) and does something (the role of the inner lambda function).

Concerning the optional question, just a trail of thoughts:

The docstring of permutations is "Return a list of all the permutations of the input."

If we think of counting the n-permutations of n, we start by:

(number of options for 1st place) * (num of options for 2nd place) * ... * (num of options for nth place)

Which is :

n * (n-1) * ...* 2 * 1 = n! And

n! = n * (n-1)!

This way, we compute the factorial recursively, and the permutations function "translates" that in a way: The mapcan-part corresponds to n, and the mapcar-part, calling permutations recursively on the remaining elements, corresponds to (n-1)!.