I'm having a problem about derangements that I'm trying to solve. Given a set $S = \{1,\ldots,n\}$, I want to generate a random derangement.
I've considered generating a permutation and checking whether or not this is a derangement, but since the ratio of derangements to permutations is quite low, this will prove to be ineffective for large $n$. For reference, the limit of the ratio is (wiki): $$\lim_{n\to\infty} {!n \over n!} = {1 \over e} \approx 0.3679\dots$$
Are there any ways to generate a derangement that guaranteed (or have a high probability) to actually result in a derangement?
It might perhaps help that my starting set is always of the same format: $S = \{1,2,3,\ldots,n\}$, although the value of $n$ might differ.
Any ideas?