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.
$\begingroup$
$\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$– EvilCommented Jul 21, 2016 at 18:21
-
1$\begingroup$ Hint: how many inversions can a single swap reverse at best? $\endgroup$– RaphaelCommented 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$– RaphaelCommented Jul 21, 2016 at 21:39
-
$\begingroup$ Single swap allows only one reversion. BTW I haven't found how to edit titles. $\endgroup$– Andrey BorovskyCommented Jul 23, 2016 at 7:05
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Jul 21, 2016 at 22:05