Permutation generation by insertion
= 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.