Number of steps to sort the array by changing order of three elements in each step

Given an array arr[] of size N consisting of unique elements in the range [0, N-1], the task is to find K which is the number of steps required to sort the given array by selecting three distinct elements and rearranging them. And also, print the indices selected in those K steps in K lines. 
 

For example, in the array {5, 4, 3, 2, 1, 0}, one possible way to sort the given array by selecting three distinct elements is to select the numbers {2, 1, 0} and sort them as {0, 1, 2} thereby making the array {5, 4, 3, 0, 1, 2}. Similarly, the remaining operations are performed and the indices selected ({3, 4, 5} in the above case) are printed in separate lines. 
 

Examples: 
 

Input: arr[] = {0, 5, 4, 3, 2, 1} 
Output: 
2 
1 2 5 
2 5 4 
Explanation: 
The above array can be sorted in 2 steps: 
Step I: We change the order of elements at indices 1, 2, 5 then the array becomes {0, 1, 5, 3, 2, 4}. 
Step II: We again change the order of elements at the indices 2, 5, 4 then the array becomes {0, 1, 2, 3, 4, 5} which is sorted.
Input: arr[] = {0, 3, 1, 6, 5, 2, 4} 
Output: -1 
Explanation: 
The above array cannot be sorted in any number of steps. 
Suppose we choose indices 1, 3, 2 then the array becomes {0, 1, 6, 3, 5, 2, 4} 
After that, we choose indices 2, 6, 4 then the array becomes {0, 1, 5, 3, 4, 2, 6}. 
Now only two elements are left unsorted so we cannot choose 3 elements so the above array cannot be sorted. We can try with any order of indices and we will always be left with 2 elements unsorted. 
 

Approach: The idea is to first count the elements which are not sorted and insert them in an unordered set. If count is 0 then we don’t need any number of steps for sorting the array so we print 0 and exit. Else, we first erase all the elements from the set for which i = A[A[i]] then we perform the following operation till the set becomes empty: 
 

• We select all the possible combination of indices(if available) such that minimum two elements will get sorted.
• Now, change the order of the elements and erase them from the set if i = A[i].
• Then, we are left with only those elements such that i = A[A[i]] and the count of those must be a multiple of 4 otherwise it is not possible to sort the elements.
• Then, we choose any two pair and perform changing the order of elements two times. Then all the four chosen elements will get sorted.
• We store all the indices which are involved in the changing of orders of elements in a vector and print it as the answer.

Let’s understand the above approach with an example. Let the array arr[] = {0, 8, 9, 10, 1, 7, 12, 4, 3, 2, 6, 5, 11}. Then: 
 

• Initially, the set will contain all the 12 elements and there are no elements such that i = A[A[i]].
• Now, {11, 5, 7} are chosen and the order of the elements are changed. Then, arr[] = {0, 8, 9, 10, 1, 5, 12, 7, 3, 2, 6, 4, 11}.
• Now, {11, 4, 1} are chosen and the order of the elements are changed. Then, arr[] = {0, 1, 9, 10, 4, 5, 12, 7, 3, 2, 6, 8, 11}.
• Now, {11, 8, 3} are chosen and the order of the elements are changed. Then, arr[] = {0, 1, 9, 3, 4, 5, 12, 7, 8, 2, 6, 10, 11}.
• Now, {11, 10, 6} are chosen and the order of the elements are changed. Then, arr[] = {0, 1, 9, 3, 4, 5, 6, 7, 8, 2, 10, 12, 11}.
• After the above step, we are left with two pairs of unsorted elements such that i = A[A[i]].
• Finally, {2, 11, 9} and {11, 9, 5} are chosen and reordered. Then, arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} which is sorted.

Below is the implementation of the above approach:
 

6
11 5 7
11 4 1
11 8 3
11 10 6
2 11 9
11 9 12

Time Complexity: O(N), where N is the size of the array.
Auxiliary space: O(N)