Derangements

The disturbances associated with a set of elements are a subset of its permutations. A fault is a permutation of elements without fixed points, that is to say without elements in the same position with the starting position of the whole.

Example: The set A,B,C has 2 faults C,A,B and B,C,A.

The faster way to generate the list of derangements of a set is to list the permutations and remove those with fixed points (elements having an identical position in the permutation and in the starting position).

Example: The set A,B,C has 6 permutations: A,B,C B,A,C C,A,B A,C,B B,C,A C,B,A. Remove the one with fixed points, ie. the permutations with A in position 1, and/or those with B in position 2 and/or those with C in position 3.
The list of derangements are the 2 remaining permutations C,A,B and B,C,A.

Counting derangements uses subfactorials. For $ n $ items, the number of derangements is equal to $ !n $ (subfactorial of $ n $): $$ !n = n! \sum_{k=0}^n \frac {(-1)^k}{k!} $$

Derangements make exponential values. The more calculations there are, the more expensive are computer servers, so the large generations must be paid.