Is there an algorithm that enumerates all permutations that are "square roots" of derangements, i.e. permutations that, when applied twice, yield a derangement? 


Other information about those kind of permutations is also welcome.



Enumerating all permutations that are "square roots" of derangements
Check out "Example 2. Permutations with no small cycles" on pg. 176 of H. Wilf's "generatingfunctionology": <https://www.math.upenn.edu/~wilf/DownldGF.html>. It explains, using generating functions, how the number of permutations in $\mathfrak{S}\_n$ you are looking for is asymptotically $\approx \frac{1}{e^{1+1/2}} n!$, just like the number of derangements is $\approx \frac{1}{e} n!$. In general the fraction of permutations with cycles all of length $>q$ is $e^{-H\_q}$ where $H\_q = 1+1/2+1/3+...+1/q$.


