recursionfunctional-programminglispcommon-lisppermutation# Understanding Peter Norvig's permutation solution in 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)))
```

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?

Solution

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

- How to loop over a multidimensional objectArray with Smarty?
- TypeScript recursive union function type
- Time complexity for recursive binary search that also prints current subarray
- How can I fix an error the error `Cannot build rewrite system for generic signature; rule length limit exceeded` in swift?
- Find the parent element of an array by the id of its child
- recursion on nested list need some support
- How do you prove termination of a recursive list length?
- python recursion i dont understand this output pls help me
- Why does recursively running `joblib.Parallel` increases the computation time?
- I'm trying to understand recursion in Tcl, but every time the recursion finishes it throws errors
- How to remove all numbers from a list in Lisp
- Calculate the total weight of segments
- Why does the expression !(cin>>word) cause infinite recursion?
- What's the best way to recursively traverse a BinaryTree in Java without void methods?
- can anybody explains the code and also recursion tree
- Is it possible to limit the depth of a recursive directory listing in S3 bucket?
- takeWhile implementation in JavaScript - Looking for better ideas
- I used a recursive function to modify a string, but if the string is too large the function returns nothing
- How to Compress Paths in SQL Server Using Recursive CTE with Node Visibility Conditions?
- Why this recursion example in ocaml doesn't work for negative number?
- Recursive loop on a list to print xml with indent
- Big O of algorithm that steps over array recursively
- Powerset of a list with equal elements in Java
- Recursion in FP-Growth Algorithm
- Passing list to function results in no case clause matching
- Convert tree-like structure formatted as a string using indentations to a list of paths
- Recursive function fails depending on lexical scoping
- Creating a list of interleaved elements: Prolog
- How to get the recursive difference formula between two columns in excel
- Get all values and associative keys as a flat array from a multidimensional array of variable depth/structure