[Math] How to directly generate permutations without fixed points

combinatoricspermutationssymmetric-groups

I have read this, however, the recursive formula still requires the complete information(all cycles with and without fixed points) of the "last step". I wonder if there is an algorithm that can directly generate permutations without fixed points?

For example, when $n=4$, the result is 

(1 2 3 4) (1 2 4 3) (1 3 2 4) (1 3 4 2) (1 4 2 3) 
(1 4 3 2) (1 2)(3 4) (1 3)(2 4) (1 4)(2 3)

some clarification

I was struggling with this part: for a given $n$, and given the partition(the number of cycles and the cycle length), how to generate all the possible, non-duplicate cycles? for example, given $n=4$ and two cycles of length 2, 2, respectively, how are (1 2)(3 4) (1 3)(2 4) (1 4)(2 3)generated?

Firstly, I understand that there is a one-to-one mapping between "derangement", and "permutation cycle representation with all cycle of length bigger than one". So solving either is a solution to my question.

Secondly, I just want to generate all such cycles/derangements for a specific n, not a specific one, or some probability, for example, given $n=4$, I expect to get the collection above, or a collection of derangements of length 4.

Thirdly, the only requirement for the method/algorithm/formula is: it does not generate all the permutations and then remove the ones that does not satisfies the condition. i.e., it directly generates the answers one by one.

Best Answer

Every permutation has a representation as a product of disjoint cycles. With suitable consideration for the commutativity of factors, this representation is unique. Since a derangement is a permutation with no fixed points, i.e. in which each disjoint cycle has length greater than one, all derangements of $\{1,2,\ldots,n\}$ can be constructed from the partitions of the set having parts of size at least two.

Indeed, given such a partition, say having $m$ parts of sizes $k_1+k_2+\ldots+k_m=n$ and each $k_i\ge2$, there will be $\prod_{i=1}^m (k_i-1)! $ corresponding derangements.

Turning this observation into an explicit algorithm provides an opportunity to discuss both generating integer partitions of $n$ and generating set partitions of $\{1,2,\ldots,n\}$.

  1. Input positive integer $n$. If $n \lt 2$, exit (no derangements).
  2. Generate all the integer partitions of $n$ whose smallest part is at least two, i.e.: $$k_1+k_2+\ldots+k_m=n$$ where $k_1\ge k_2\ge \ldots \ge k_m \ge 2$.
  3. For each such integer partition of $n$, generate all the set partitions of $\{1,2,\ldots,n\}$ whose subsets have corresponding sizes $k_i$.
  4. For each such set partition of $\{1,2,\ldots,n\}$, generate all the disjoint cyclic decompositions where the cycles have the parts of the set partition as their underlying disjoint sets.
  5. Output such a permutation (derangement).

Each step between the first one and the fifth one can be accomplished in at least one and possibly in multiple ways. Since each step depends on the results of the previous step, we generate the outputs as leaves of a tree of dependent choices. To output all possible derangements requires backtracking through this tree of choices, i.e. when all possibilities for a given step are exhausted, control passes back the the previous step to continue generation.

To do: Notes on implementation of steps 2,3,4,5

Related Question