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.

Improve this question
$\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).

Improve this answer
$\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