4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What you've listed is all permutations (not cycles) with no fixed points. Is that what you want? A transposition means a cycle of length $2$. Permutations with no fixed points are called derangements. $\endgroup$ – Qudit Mar 24 '17 at 4:52
  • $\begingroup$ @Qudit that's the original problem I want to solve, but I just got algorithms either removes or skips the ones not satisfying the condition. So I am wondering if there is some advanced theory that can solve the problem directly. $\endgroup$ – happy fish Mar 24 '17 at 4:59
  • $\begingroup$ In that case you may want to clarify your question above. $\endgroup$ – Qudit Mar 24 '17 at 5:01
  • 1
    $\begingroup$ Also, while it's possible to make such an algorithm, it's also pointless from an efficiency protective because asymptotically the number of derangements is $n! / e$ so it only saves at most a constant factor. $\endgroup$ – Qudit Mar 24 '17 at 5:25
  • 2
    $\begingroup$ Do you want an algorithm that generates all derangements, or an algorithm that randomly generates single derangements? if the latter, do you want it to produce every derangement of $n$ numbers with equal probability? It's really unclear what you're asking. $\endgroup$ – Greg Martin Mar 24 '17 at 16:53
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thanks for answering my question, I have edited the question to include more details. $\endgroup$ – happy fish Mar 25 '17 at 12:47
  • $\begingroup$ Thanks for the clarification. I'll update my Answer with more focused details. $\endgroup$ – hardmath Mar 25 '17 at 13:03
1
$\begingroup$

Here is an algorithm in pseudocode

function derangement(size : Nat) : List of List of Nat
   return derangement_inner(1, { 1 .. size })


function derangement_inner(index : Nat, candidates : Set of Nat) : List of List of Nat 
   if (candidates is empty) then
       return [[]]
   else
       rl = []
       foreach element in candidates\{index}
         derangements_for_index = map ( x ↦ element :: x) derangement_inner(index + 1, candidates\{element})
         rl = rl ++ derangements_for_index
       return rl

( "::" is your cons, "\" is the set difference operator, and "++" is your list concatenation operator). Basically it is a modification of the recursive permutation creator that skips over the fixed points.

$\endgroup$
  • $\begingroup$ Yes it is. I've corrected the spelling. $\endgroup$ – Q the Platypus Mar 26 '17 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.