recursion - 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.