 Permutation generation by insertion

Generate every permutation of a finite list by recursively permuting its tail and inserting its head into each possible position. For $n$ distinct input elements, every shorter permutation has $n$ insertion positions, giving $n(n-1)!=n!$ results. Removing the distinguished head reconstructs the unique shorter permutation and insertion position.