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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.