Associated Topics || Dr. Math Home || Search Dr. Math

### Algorithm for Derangements

```Date: 01/11/2003 at 10:12:31
From: Tony Silvaggio
Subject: Algorithm for derangements

I have been looking for a recursive algorithm to find all possible
derangements of a set n. I am very familiar with the math involved but
cannot think of a method to generate the derangements.

I have found a method to generate all permutations and eliminate the
ones that are not derangements. This is easy. But is there a way to
simply find only the derangements, thereby making the algorithm
simpler and more efficient?
```

```
Date: 01/11/2003 at 10:37:29
From: Doctor Tom
Subject: Re: Algorithm for derangements

Hi Tony,

A derangement is a permutation that moves everything, so in cycle
notation, you want to consider only permutations that have only cycles
of length 2 or more. (I assume that we use the notation where
everything is listed in the cycles, so that the permutation of 3 items
that swaps 1 and 2 would be written as: "(1 2)(3)", and it is
obviously not a derangement since the 3 sits in a cycle of its own.)

So to show the idea, look at derangements of 8 items:

I'll classify cycle patterns by the longest cycle:

8: (x x x x x x x x)
7: none
6: (x x x x x x)(x x)
5: (x x x x x)(x x x)
4: (x x x x)(x x x x) and (x x)(x x)(x x x x)
3: (x x)(x x x)(x x x)
2: (x x)(x x)(x x)(x x)

This list should be easy to generate.

Now let's look at filling in all the possibilities for, say,
(x x)(x x x)(x x x)

You have to choose 2 items to fill the 2-cycles and 6 items to fill
the 3-cycles. For each such selection, there's only one way to fill in
the 2-cycle, but now things get a little ugly, since (1 2 3)(4 5 6) is
the same as (4 5 6)(1 2 3) is the same as (1 2 3)(6 5 4).

First, we'll agree to list each cycle starting with its smallest
number, and only one of the cycles has a 1 in it, so list that first.
Now it's easy.

Things do get messier if you have to deal with ones like
(x x)(x x)(x x)(x x), but I guess this can just be done recursively:
The first cycle has 1 in it, so for each possible pair in the cycle,
there are 6 numbers left over. Use the smallest available to fill the
first slot in the next cycle, and for each of the ways to pair it up,
there are 4 items available for the last two cycles, use the smallest,
et cetera.

It seems to me that the code will be a bit tricky, but not terribly
so. And it will be easy to test, since you can list out by hand the
results you expect in the proper order for some of the smaller
derangements and you can check to see what your routine is doing.

This is a pretty cool problem!

- Doctor Tom, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 01/11/2003 at 11:21:33
From: Doctor Tom
Subject: Re: Algorithm for derangements

How about if you write a recursive routine that takes as inputs two
sets (you figure out the best data structure to represent them) and a
previously printed partial permutation.

Suppose the sets are strings and the items to be deranged are letters,
so "ace" is the set consisting of a, c, and e:

The first set represents the unplaced items, and the second, the
unfilled slots. Recursively call the routine with each valid placement
of an item into an unfilled slot with smaller input sets.

Suppose the output looks like this for a typical derangement of four
items:

(ac)(ca)(bd)(db)  means a to slot c, c to slot a, etc.

In the running of the code to get derangements of 5 items,
a, b, c, d, e, here's the typical situation:

print_derangements("(ac)", "bcde", "abde")

This will call itself three times, putting b into a, d, and e.  When
it tries the b into a derangement, the next level of recursion
will look like this:

print_derangements("(ac)(ba)", "cde", "bde")

If you get to one item and one slot and the item is different from
the slot, print the initial string followed by the final pairing and
return.

Should work great!  (I think.)

- Doctor Tom, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search