Preliminaries

For this article, array indexes start at 1...n. A derangement is a permutation \(P\left(A\right)\) of an array \(A\) such that all elements are not in their original position. For example, let \(A=\left\{1,2,3,4,5\right\}\). Then \(P\left(A\right)=\left\{3,1,2,5,4\right\}\) is a derangement.
Given the nature of derangements, we are interested in the following questions:
  1. Can we count the total number of derangements for an n-element array?
  2. Can we generate all derangements for an n-element array?
  3. Can we generate a single derangement in a sequence (like next_permutation)?
  4. can we generate a single derangement at random (requires uniform probability)?
Furthermore, we are not interested in a rejection-based algorithm which is commonly seen. We are interested in an algorithm that generates only the desired set of solutions.

Counting derangements