Generating all permutations: a non-recursive algorithm

A natural idea for generating all permutations of n elements is to write a recursive algorithm with O(n!) time complexity. The algorithm used in C++ STL function next_permutation is a more efficient solution --- it generates all unique permutations non-recursively and moreover in lexicographic order. The algorithm is given by the great computer scientist Donald Knuth in his book The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations. Here is his Draft of Section 7.2.1.2: Generating All Permutations.