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?

Gibert

I am pretty sure, that I am not in the position to tell you how Peter Norvig thinks ;-) but if you check the documentation of mapcan and replace it in the code with a mapcar you will see the difference pretty clearly. Furthermore if you trace permutations you see the lambdas working as described in the comment. – Oriya

Thank you for the comment. Honestly, the documentation of mapcan doesn't help much because it doesn't show any real-life use cases of it. trace doesn't help much either because it shows only 2 invocations of the permutations one with the input and one with the final output, i.e. it doesn't show the individual progressions of those mapcan and mapcar The only helpful thing is to replace the mapcan with mapcar as it shows the progression but again it doesn't show clearly how those 2 lambdas work in perfect harmony to produce the correct output, nor explain when to use mapcan. – Gibert

What is your input data? If you start with a simple test case like (a b) and then increase to (a b c) it should show a difference in the trace. – Oriya

For an input of '(a b) trace output is: 1. Trace: (PERMUTATION '(A B)) 1. Trace: PERMUTATION ==> ((A B) (B A)) i.e. only the input and output repeating. – Gibert

Well, for two elements you have only two permutations. If there is nothing special in your CL implementation I would expect more information for three elements in trace‘s output. – Oriya

It was clisp which gave only 2 trace outputs for a 2 elements input '(a b) Obviously something was wrong with it so I've tried it on sbcl with 3 elements input '(a b c) and it gave 31 lines of trace output and it's quite informative. Here it is Thank you for the comment, it's helpful. – Gibert

Answer 1

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

Antimicrobial

Answer 2

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.

Mating

Answer 3

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)!.

Hosiery

Thank you for the answer. It's well-written and quite informative however, it seems basically to go over the already apparent implications of the code and not adequately show the inner workings of those 2 lambdas and explain the 'rationale' behind. And there seems to be an error in the example where mapcar is used in place of mapcan In my take it gave (((1 (2 (3))) (1 (3 (2)))) ((2 (1 (3)))... i.e. with many more parenthesis. – Gibert

Thank you for pointing out the error in the code result (edited my answer). Concerning the inner workings and the rationale of lambdas, do you mean in general (like why the lambda-expressions, alternatives, etc), or more of a trace explanation? – Hosiery

Answer 4

A permutation of bag is a sequence with the same elements as bag, though possibly in a different order.

If we write bag as (e1 ... en), then the set of all permutations contains all permutations where e1 is in first position, all the permutations where e2 is in first positions etc. and all the permutations where en is the first element.

This way of partitioning the permutations is what the algorithm exploits, by recursively computing all the permutations where each element is in first position.

(defun permutations (bag)
  (if (null bag)
      '(())
      (mapcan #'(lambda (e)
                  (mapcar #'(lambda (p) (cons e p))
                          (permutations (remove e bag))))
              bag)))

The innermost lambda:

#'(lambda (p) (cons e p)

is interpreted as:

Given a permutation p, which is a list of values, return a new permutation with element e in front.

It is passed to mapcar for a list of permutations:

(mapcar #'(lambda (p) (cons e p))
          (permutations (remove e bag)))

The meaning of the call to mapcar is thus:

Compute all the permutations of the subset obtained by removing e from bag. This gives a list of permutations, each one being a list of values that do not contain e. For all of those lists, add e in front. The result of mapcar is a list of permutations where e is the element in front of each permutation.

More concretely, if you have a bag (1 2 3), and if e is 1, then first you remove 1 from the bag, which is (2 3), you compute all the permutations recursively, which is ((2 3) (3 2)), and for all the permutations in that list you add 1 in front of the permutations; you obtain ((1 2 3) (1 3 2)).

Now, notice that this does not contain all the possible permutations of (1 2 3).

You want also to compute the permutations where e is 2, so you remove 2 and compute the permutations, which are ((1 3) (3 1)), and you add 2 in front, for another list of permutations, namely ((2 1 3) (2 3 1)).

Finally, you also want to do the same when e is 3. Let's skip the intermediate computations, the result is ((3 1 2) (3 2 1)).

All the intermediate results are different permutations of (1 2 3) that cover, without duplicates, all the permutations of the initial bag:

e = 1 : ((1 2 3) (1 3 2))
e = 2 : ((2 1 3) (2 3 1))
e = 3 : ((3 1 2) (3 2 1))

When we append all the lists together, we obtain the list of all the permutations of (1 2 3):

((1 2 3) (1 3 2)
 (2 1 3) (2 3 1)
 (3 1 2) (3 2 1))

That's the purpose of the call to mapcan: (mapcan ... bag) computes lists of permutations of bag for each element of bag and append them to compute the complete set of permutations.

I don't know how Norvig thought about writing this code in particular, but the recursive algorithms for computing permutations were already documented.

See for example Permutation Generation Methods (R. Sedgewick, 1977). This paper is mostly concerned about computing permutations over vectors, not linked lists, and one of the best algorithm in this category (that minimizes swaps) is Heap's algorithm.

For linked lists, I found this paper Functional Programs for Generating Permutations. by Topor in 1982 (PAIP was published in 1991).

Camerlengo

there's also this. :) – Ghassan

Ah yes I remember that – Camerlengo

Answer 5

Good code in a nice readable language doesn't need to be brilliant. It's better when it's just simple and self-evident.

So let's re-write that 'brilliant' code down in some readable pseudocode and see if it clears up a bit.

(permutations [])  =  [ [] ]
(permutations bag) = 

  = (mapcan #'(lambda (e)
                  (mapcar #'(lambda (p) (cons e p))
                          (permutations (remove e bag))))
              bag)

  = (concat    ;; (concat list) = (reduce #'nconc list)
     (mapcar #'(lambda (e)
                  (mapcar #'(lambda (p) (cons e p))
                          (permutations (remove e bag))))
              bag))

  = concat  { FOR e IN bag :
                YIELD { FOR p IN (permutations (remove e bag)) :
                          YIELD [e, ...p] } }

  =         { FOR e IN bag :
                      { FOR p IN (permutations (remove e bag)) :
                          YIELD [e, ...p] } }

  = [[e,...p] FOR e IN bag,
                        FOR p IN (permutations (remove e bag)) ]

  = (loop  for e in bag   nconc               ;; appending
        (loop  for p in (permutations (remove e bag))
             nconc   (list (cons e p)) ))
        ;;   collect       (cons e p)

I rest my case.

Incidentally, now that the code's meaning has cleared up, we can see that the code is not quite right: it removes elements by value, while permutations belongs to combinatorics which is purely positional. _{(The second and third link below do that; the second link also contains a version directly corresponding to the one here).}

see also:

• Nested Loops Using Loop Macro in Common Lisp
• How does this complex recursive code work?
• How to generate all the permutations of elements in a list one at a time in Lisp?
• Finding all possible permutations of the characters in a set of strings using recursion
• "Shrinking Domain" paradigm
• Haskell Monad - How does Monad on list work?

---

So what is really going on here is generation (nay yielding) of elements of the result list one by one inside two nested loops. The use of mapcan = concat ... mapcar ... is just an implementational detail.

Or we could use the M word, say that the essence of Monad is flatMap is mapcan, and its meaning generalized nested loops.

---

Ghassan