The classical 'correct' way of shuffling a deck of $n$ items is to use the Fisher-Yates shuffle:
for (i = n; i > 1; i--) {
choose j randomly in [1..i];
swap deck[i] and deck[j];
}
It's not hard to show that this algorithm works: there are $n!$ different paths through the code (there are $n$ possible choices for $j$ in the first iteration of the loop, then $n-1$ choices in the second iteration, giving $n\cdot(n-1)\cdot(n-2)\cdot\ldots=n!$ possbilities in total), and each of these generates a different permutation.
Now consider an identical algorithm, but with $j$ chosen randomly from the range $[1\ldots (i-1)]$; in other words, at each step, the value at position $i$ is explicitly swapped with some other value (it can't be left in place). It's straightforward to show that every permutation that can be generated this way is a derangement: when we reach entry $k$ in the array, either its value is still $k$, in which case it's swapped with a lower entry and then entry $k$ is locked at a value different from $k$, or its value is no longer $k$, in which case $k$ was swapped into some entry of higher index and it can never be swapped back 'home'. On the other hand, not all derangements can be obtained this way; for one thing, it's clear that the number of paths is $(n-1)!$, which is smaller than the number of derangements $D_n=n!(1-\frac1{2!}+\frac1{3!}-\ldots\pm\frac1{n!})$ for all $n\gt 3$; for another thing, all permutations generated by this algorithm for a given $n$ have the same parity (which depends directly on the parity of $n$).
Is there any 'nicer' characterization of the permutations that can be obtained this way than the one given by this algorithm? (Equivalently, I think: is there a 'nice' way of describing the embedding $\mathcal{S}_{n-1}\hookrightarrow\mathcal{S}_n$ generated by this algorithm?)