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

I thought about this some more.

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/