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$
  • $\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 '16 at 18:21
  • 1
    $\begingroup$ Hint: how many inversions can a single swap reverse at best? $\endgroup$ – Raphael Jul 21 '16 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 '16 at 21:39
  • $\begingroup$ Single swap allows only one reversion. BTW I haven't found how to edit titles. $\endgroup$ – Andrey Borovsky Jul 23 '16 at 7:05
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, privacy policy and cookie policy

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