= 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. Thus
$$
P(0)=1=0!,\qquad P(n)=nP(n-1),\qquad
\boxed{P(n)=n!.}
$$
Length 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.
Back to article page
