Alphabetizing Lists with Transpositions
by
John Kiltinen

Thursday, October 2, 2003
4:00 p.m.
New Science 1205

Suppose you have a list consisting of some A's and some B's that is scrambled and you want to get the list into alphabetical order.  Suppose that the method of reorganizing the list is to do swaps of pairs of entries.  On average, how many swaps will it take to get this list into order? (The graphic shows such a scrambled list with 9 A's and 11 B's.)  Getting the list into order is trivial, but knowing how many swaps it will take on average is not.

 This question is motivated by the simplest of the puzzles in my Permutation Puzzles Package of software.  (It is the puzzle I thought would never amount to much when it grew up and here it is generating interesting problems.)  In the talk, I will present a solution to the question posed here.  The work involved some enjoyable collaboration with colleagues Qinghong Zhang and Sujay Datta.  There are some remaining unanswered questions related to efficient algorithms and expected numbers of swaps when there are more than two different letters.