On Thu, May 7, 2015 at 3:01 PM, Leo Broukhis <leob@mailcom.com> wrote:
What if we allow combining disjoint same distance transpositions, e.g.
1234567890 <-> 3412765098
That reduces the diameter to ceiling(log_2(n)); we can find a permutation of this form that sends half of the objects being permuted to the right place, then multiply by another that fixes these and sends half of the remainder to the right place, and so forth.
The ceiling(log_2(n)) estimate seems intuitively right, as it takes at most that number of bit swaps to reverse a word, but the observation is wrong. When doing a reversal, all pairwise distances are different, therefore the first swap can send no more than 2 objects to the right place. We win only by incremental adjustments. And still, it is not obvious that an arbitrary permutation will be decomposable as easily as the reversal.
Sorry, I didn't notice the "same distance" clause. log_2(n) is correct if we allow combining any set of disjoint transpositions, which is not the question you asked. Same-distance transpositions sounds like an interesting problem; I'll have to think about it more. Andy -- Andy.Latto@pobox.com