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.