Sort permutation of N natural numbers using triple cyclic right swaps | C ++ implementation to find the number of operations required to sort the elements of the array ; Function to sort the permutation with the given operations ; Visited array to check the array element is at correct position or not ; Loop to iterate over the elements of the given array ; Condition to check if the elements is at its correct position ; Condition to check if the element is included in any previous cyclic rotations ; Loop to find the cyclic rotations in required ; Condition to check if the cyclic rotation is a valid rotation ; Loop to find the index of the cyclic rotation for the current index ; Condition to if the cyclic rotation is a valid rotation ; Loop to find all the valid operations required to sort the permutation ; Total operation required ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE void sortPermutation ( ll arr [ ] , ll n ) { vector < pair < ll , pair < ll , ll > > > ans ; vector < ll > p ; bool visited [ 200005 ] = { 0 } ; for ( ll i = 1 ; i <= n ; i ++ ) { if ( arr [ i ] == i ) { visited [ i ] = 1 ; continue ; } else { if ( ! visited [ i ] ) { ll x = i ; vector < ll > v ; while ( ! visited [ x ] ) { visited [ x ] = 1 ; v . push_back ( x ) ; x = arr [ x ] ; } if ( ( v . size ( ) - 3 ) % 2 == 0 ) { for ( ll i = 1 ; i < v . size ( ) ; i += 2 ) { ans . push_back ( make_pair ( v [ 0 ] , make_pair ( v [ i ] , v [ i + 1 ] ) ) ) ; } continue ; } p . push_back ( v [ 0 ] ) ; p . push_back ( v [ v . size ( ) - 1 ] ) ; for ( ll i = 1 ; i < v . size ( ) - 1 ; i += 2 ) { ans . push_back ( make_pair ( v [ 0 ] , make_pair ( v [ i ] , v [ i + 1 ] ) ) ) ; } } } } if ( p . size ( ) % 4 ) { cout << -1 << " STRNEWLINE " ; return ; } for ( ll i = 0 ; i < p . size ( ) ; i += 4 ) { ans . push_back ( make_pair ( p [ i ] , make_pair ( p [ i + 1 ] , p [ i + 2 ] ) ) ) ; ans . push_back ( make_pair ( p [ i + 2 ] , make_pair ( p [ i ] , p [ i + 3 ] ) ) ) ; } cout << ans . size ( ) << " STRNEWLINE " ; for ( ll i = 0 ; i < ans . size ( ) ; i ++ ) { cout << ans [ i ] . first << " ▁ " << ans [ i ] . second . first << " ▁ " << ans [ i ] . second . second << " STRNEWLINE " ; } } int main ( ) { ll arr [ ] = { 0 , 3 , 2 , 4 , 1 } ; ll n = 4 ; sortPermutation ( arr , n ) ; return 0 ; }