0
$\begingroup$

Consider you have a permutation of $1$ to $n$ in an array $array$. Now select three distinct indices $i$,$j$,$k$, there is no need to be sorted. Let $array_i$, $array_j$ and $array_k$ be the values at those indices and now you make a right shift to it, that is $new$ $array_i$= $old$ $array_j$ and $new$ $array_j$= $ old$ $array_k$ and $new$ $array_k$=$old$ $array_i$. Find the minimum number of operations required to sort the array or if is impossible how to determine it.

Example : Consider $array= [3,1,2]$; consider indices $(1,3,2)$ in the given order after applying one operation it is $s =[1,3,2]$.

Can anybody share your approach.

$\endgroup$
5
  • $\begingroup$ @Yuval Filmus can you suggest any algorithm? $\endgroup$ – user120540 May 3 '20 at 10:07
  • $\begingroup$ By the way, applying the operation $(1,3,2)$ to the array $[3,1,2]$ gives the array $[2,3,1]$. If we instead applied $(1,2,3)$, we would get $[1,2,3]$. $\endgroup$ – Yuval Filmus May 3 '20 at 10:52
  • $\begingroup$ The permutation $[3,1,2]$ is even. It's a 3-cycle. $\endgroup$ – Yuval Filmus May 3 '20 at 11:10
  • $\begingroup$ Oh sorry ,and Thank you for the answer $\endgroup$ – user120540 May 3 '20 at 11:11
  • 1
    $\begingroup$ This question appears to be about a problem from an ongoing contest. Please edit the question to clearly indicate the source of your problem. I will close this question for now while the source is unclear. We require you to attribute the source of all copied material. $\endgroup$ – D.W. May 3 '20 at 15:42
1
$\begingroup$

Your operations correspond to applying a 3-cycle on the input permutation. You can reach the identity by applying 3-cycles iff the input permutation is even. Given the cycle decomposition of the input permutation, it shouldn't be hard to answer your question (though the answer is not immediate).

$\endgroup$
8
  • $\begingroup$ You will have to look these terms up. The Wikipedia page on the symmetric group should contain all the information you need (and a lot of it that you don't need). $\endgroup$ – Yuval Filmus May 3 '20 at 10:16
  • $\begingroup$ See also this question; the alternating group consists of all even permutations. $\endgroup$ – Yuval Filmus May 3 '20 at 10:17
  • $\begingroup$ No, you need to use permutations. $\endgroup$ – Yuval Filmus May 3 '20 at 10:36
  • $\begingroup$ I already gave a hint. That's my answer. If you are not familiar with permutations and their cycle decomposition, I think you'll have a hard time solving this question. $\endgroup$ – Yuval Filmus May 3 '20 at 10:39
  • 1
    $\begingroup$ I think you just helped someone with an open coding contest problem. $\endgroup$ – D.W. May 3 '20 at 15:43