Creating single-cycle permutations There was this one time I came up with a small permutation that had a block size of 16 bits. This was small enough to compute every mapping. I then iterated the mapping starting with zero to see how many iterations it would take to return to zero. The number was less than half of $2^{16}$.

For whatever reason, let's say a person needs a pseudorandom permutation that has only one cycle. Perhaps they need to make a single-cycle S-box or they want to use the permutation to create a non-linear tweak to the plaintext input of a block cipher (each block's tweak is the result of successive iterations instead of increments of one). First thing that comes to my mind is a full-period LCG, but when I tried this for making an S-box ($f(x) = (37 \cdot x + 11) \mbox{ mod } 256$), the results seemed rather orderly. This wouldn't matter for a tweak for plaintext blocks, but it seems desirable to simply not have that property of orderliness. So, what are some way of generating/constructing single-cycle permutations?
The obvious way to construct such a pseudorandom single-cycle permutation is to take a pseudorandom permutation $P$ (which need not be single-cycle), a simple fixed single-cycle permutation $Inc$ (e.g. just increment the value by 1), and construct:

$$S = P^{-1} \ \circ Inc \ \circ P $$

That is, to evaluate $S(x)$, you first apply the permutation $P$ to $x$, then the permutation $Inc$, and then the permutation $P^{-1}$, which is the inverse of the permutation $P$.

Things that should be obvious:


$S$ is a single cycle permutation
Every single cycle permutation can be expressed this way with an appropriate choice of $P$
(Less obvious) if $P$ is selected uniformly over all permutations, then $S$ is selected uniformly over all single-cycle permutations.