2
$\begingroup$

Let's have two permutations $A$ and $B$ of $n$ numbers. What is the minimal number $m$ of transpositions to transform $A$ to B in the worst case? After analysing some algorithms my guess is that $m \sim n^2$ but I cannot find a formal proof.

$\endgroup$
4
  • $\begingroup$ So you are doing something like sorting and counting minimal swaps possible? And it seems quite $O(n)$ to me if I understood your intentions. $\endgroup$
    – Evil
    Jul 21, 2016 at 18:21
  • 1
    $\begingroup$ Hint: how many inversions can a single swap reverse at best? $\endgroup$
    – Raphael
    Jul 21, 2016 at 21:39
  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Jul 21, 2016 at 21:39
  • $\begingroup$ Single swap allows only one reversion. BTW I haven't found how to edit titles. $\endgroup$ Jul 23, 2016 at 7:05

1 Answer 1

1
$\begingroup$

If your transpositions form a permutation $\pi$ then (using the appropriate convention for multiplication) $A\pi = B$ and so $\pi = A^{-1} B$. This shows that we can assume without loss of generality that $A$ is the identity, and the question now becomes: how many transpositions do we need to multiply in the worst case to get any particular permutation? This might be a question you already know how to answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.