Generating a random derangement

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?

Solution 1:

The algorithm that joriki linked to is described in more detail in Martínez, Conrado, Alois Panholzer, and Helmut Prodinger. "Generating Random Derangements." ANALCO. 2008. http://epubs.siam.org/doi/pdf/10.1137/1.9781611972986.7

It's NOT a rejection-based algorithm (I'm not sure why Mythio thinks it is). The permutation is generated one element at a time, from high index to low index, and the result is a derangement 100% of the time.

There is something like a rejection component in the internal loop, when choosing the next element. The remaining candidates are classified as "marked" and "unmarked" and the algorithm must choose one of the unmarked ones. The authors implemented this as a trial-and-error process, but it could instead be implemented as a set, which would reduce each element selection to a single RNG call.

After an element is selected there is another RNG call to decide marked/unmarked.