Transpositions and S_n

According to official TV listings, there is an upcoming episode of Futurama called "The Prisoner of Benda" involving a device which allows people to switch minds. The title seems to be a riff off "The Prisoner of Zenda", a novel in which a fictional king is abducted and a distant relative who happens to look like the king is forced to impersonate him.

A few months ago, one of the staff writers for Futurama leaked the following photo of a script from the new season:

(Photo hosted by Futurama Madhouse.)

The page appears to be a lemma concerning the number of transpositions required to construct a permutation on the first n elements of the set {1, 2, ..., n, A, B} when one element of the transposition is one of the first n indices and the other element is one of the two auxiliary indices. Constructing permutations out of transpositions via algorithms such as selection sort and bubble sort is of course well-known; the only wrinkle here seems to be the auxiliary set.

It seems fairly straightforward to construct the denouement of the episode (or an approximation thereof) from this information: our heroes start fooling around with the mind-swapping device and somehow end up imprisoned. They discover that the device has a limited number of charges and need to undo the mind-swapping, but they're positioned such that one end of the device is in their cell and the other end of the device is in an adjacent cell inhabited by two other people/animals/potted plants/whatever. However, it seems to me that only one auxiliary element is needed to construct a k-cycle, and that it only requires (k+1) moves, so I could well be missing something here.

Here's the basic algorithm: assume we have a k-cycle which does not fix 1; otherwise this reduces to the (k-1) case. Write out the n-cycle in two-row form. For example, the permutation 2->4->1->3->2 on 4 elements would be written as


Swap 1 and A:


Swap A with whatever element belongs in the spot it's in now (in this example, 4):


Repeat the step above (in this case, swap A and 2), and continue until done. Because the original permutation was a n-cycle, each step will involve swapping A with a different element of the set {1, 2, ..., n}, and the final step will undo the original permutation, with A in its original place:





More formally, given a n-cycle permutation sigma on {1, 2, ..., n}, apply the transposition (A, 1), then (A, sigma^(-1) 1), then (A, sigma^(-2) 1), ..., (A, sigma^(-(n-1)) 1), then (A, 1) again.

Producer David X. Cohen claimed that writer Ken Keeler (who has a Ph.D. in control theory from Harvard) penned this theorem specifically for the episode. Calling it a "theorem" is a stretch (it's about the level of a homework problem for an introductory undergrad course in discrete math), but nonetheless it's amusing that Keeler managed to work it in.

EDIT, 8/19/10: The actual episode aired tonight, and the wrinkle is that once two bodies use the mind-swapper, that same pair can never use it again. In this case, two extra bodies are both necessary (we used the A, 1 swap twice above, so the above method won't work) and sufficient to undo any permutation on {1, 2, ..., n}.

Suppose the minds in bodies {1, 2, ..., n} are permuted by a cyclic shift:


Pick some i strictly less than n, and apply the transpositions on the pairs of bodies (A,1), (A,2), ..., (A,i) in that order:






Now apply (B, i+1), (B, i+2), ..., (B, n) in that order:






Now apply (A, i+1) and (B, 1):


Every swap takes place between one element of {A,B} and one element of {1,2,...,n}, so the process by which {1,2,...,n} got swapped is irrelevant, and none of the swaps in our procedure are duplicated.

If the set {1,2,...,n} forms the only cycle that needs to be unpermuted, swap A and B. Otherwise, apply the same procedure to all disjoint cycles in succession. If there's an odd number of disjoint cycles, then A and B will need to be swapped at the end.

EDIT, 8/20/10: Welcome both of you io9 readers. Out of concern that somebody might actually read this, I've expanded the explanation of the algorithm slightly.


andrew said...

Cool plot none-the-less.

mike said...

Veeeerry interesting. :) Thanks for the write up! Love it! :D

simon@kins said...

Ahhh, but wouldn't it be sweeter if you did it in LaTex?