How does Knuth's second algorithm to calculate permutations work?

Question

I have started reading the Art of Computer Programming Volume 1 by Knuth. The first half of the book is basic concepts in maths. On page 45 there is an algorithm to obtain the next (amount of) permutations of 231.

From

2 3 1 1/2    2 3 1 3/2    2 3 1 5/2    2 3 1 7/2 

he goes to

3 4 2 1      3 4 1 2      2 4 1 3      2 3 1 4

by "renaming" as can be seen here:

I have no idea how he accomplishes this and there is no further explanation. Can someone explain more about this?

Answer 1

Apparently,

1. You are given a permutation $(a_1,a_2,\cdots, a_{n-1})$ of length $n-1$, such as $(2,3,1)$.
2. Spawn $n$ $n$-tuples of the form $(a_1,a_2,\cdots, a_{n-1},k)$ for $k=1,2,\ldots,n$. I say "tuple" instead of "permutation" because it can happen that $a_i=k$ for some $i$; i.e. these tuples are not yet permutations. For the given example, we get $(2,3,1,1),(2,3,1,2),(2,3,1,3),(2,3,1,4)$.
3. For each tuple $(a_1,a_2,\cdots, a_{n-1},\color{red}{k})$, let $b_1<b_2<\cdots<b_{n-1}$ be the members of $\{1,2,\ldots,n\}\setminus\{\color{red}{k}\}$. That is, $b_i=i$ when $i<k$ and $b_i=i+1$ when $i>k$. Now, generate a permutation $(b_{a_1},b_{a_2},\ldots,b_{a_{n-1}},k)$. For example, given the tuple $(\color{blue}{2},\color{blue}{3},\color{blue}{1},\color{red}{1})$ in the previous step, the set of the other numbers than $\color{red}{1}$ are $\{1,2,3,4\}\setminus\{\color{red}{1}\}=\{\color{green}{2},\color{green}{3},\color{green}{4}\}$. If we put the numbers $\color{green}{2},\color{green}{3},\color{green}{4}$ in the order of $\color{blue}{2}$nd, $\color{blue}{3}$rd and $\color{blue}{1}$st, we get $\color{green}{3},\color{green}{4},\color{green}{2}$. So, the permutation we get is $(\color{green}{3},\color{green}{4},\color{green}{2},\color{red}{1})$.