  We show how to generate random derangements efficiently by two different
techniques: random restricted transpositions and sequential importance
sampling. The algorithm employing restricted transpositions can also be used to
generate random fixed-point-free involutions only, a.k.a. random perfect
matchings on the complete graph. Our data indicate that the algorithms generate
random samples with the expected distribution of cycle lengths, which we
derive, and for relatively small samples, which can actually be very large in
absolute numbers, we argue that they generate samples indistinguishable from
the uniform distribution. Both algorithms are simple to understand and
implement and possess a performance comparable to or better than those of
currently known methods. Simulations suggest that the mixing time of the
algorithm based on random restricted transpositions (in the total variance
distance with respect to the distribution of cycle lengths) is
$O(n^{a}\log{n}^{2})$ with $a \simeq \frac{1}{2}$ and $n$ the length of the
derangement. We prove that the sequential importance sampling algorithm
generates random derangements in $O(n)$ time with probability $O(1/n)$ of
failing.
