Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 2 / b / Solution

Use permutation generation by insertion: recursively arrange the tail, then insert the removed head in every possible position.

inserts x [] = [[x]]
inserts x (y:ys) = (x:y:ys) : map (y:) (inserts x ys)

perms [] = [[]]
perms (x:xs) = concat (map (inserts x) (perms xs))

The map function in inserts prefixes y to each placement after the first position. For a list of length $k$, the number of results obeys $I(0)=1$ and $I(k+1)=1+I(k)$, so mathematical induction gives $I(k)=k+1$. Every result still contains the same $k$ old elements and the one inserted element.

Let $P(n)$ be the length of perms xs for an input of length $n$. There is exactly one permutation of the empty list, namely the empty list itself: hence perms [] is [[]], with length one. For a nonempty input, each recursively obtained permutation has length $n-1$ and gives $n$ placements. ThusLength alone would not exclude repeated answers. Since the input elements are distinct, removing the distinguished element $x$ from any result uniquely recovers both its placement and the shorter permutation. Hence different construction choices give different outputs, and every desired permutation is obtained by inserting $x$ into its restriction to xs. For [a,b,c], this code yields [a,b,c], [b,a,c], [b,c,a], [a,c,b], [c,a,b], [c,b,a], each exactly once.