Sort permutation of N natural numbers using triple cyclic right swaps | 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 athe valid operations required to sort the permutation ; Total operation required ; Driver Code ; Function Call
def sortPermutation ( arr , n ) : NEW_LINE INDENT ans = [ ] NEW_LINE p = [ ] NEW_LINE visited = [ 0 ] * 200005 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( arr [ i ] == i ) : NEW_LINE INDENT visited [ i ] = 1 NEW_LINE continue NEW_LINE DEDENT else : NEW_LINE INDENT if ( visited [ i ] == False ) : NEW_LINE INDENT x = i NEW_LINE v = [ ] NEW_LINE while ( visited [ x ] == False ) : NEW_LINE INDENT visited [ x ] = 1 NEW_LINE v . append ( x ) NEW_LINE x = arr [ x ] NEW_LINE DEDENT if ( ( len ( v ) - 3 ) % 2 == 0 ) : NEW_LINE INDENT for i in range ( 1 , len ( v ) , 2 ) : NEW_LINE INDENT ans . append ( [ v [ 0 ] , v [ i ] , v [ i + 1 ] ] ) NEW_LINE DEDENT continue NEW_LINE DEDENT p . append ( v [ 0 ] ) NEW_LINE p . append ( v [ len ( v ) - 1 ] ) NEW_LINE for i in range ( 1 , len ( v ) - 1 , 2 ) : NEW_LINE INDENT ans . append ( [ v [ 0 ] , v [ i ] , v [ i + 1 ] ] ) NEW_LINE DEDENT DEDENT DEDENT DEDENT if ( len ( p ) % 4 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE return NEW_LINE DEDENT for i in range ( 0 , len ( p ) , 4 ) : NEW_LINE INDENT ans . append ( [ p [ i ] , p [ i + 1 ] , p [ i + 2 ] ] ) NEW_LINE ans . append ( p [ i [ + 2 ] , p [ i ] , p [ i + 3 ] ] ) NEW_LINE DEDENT print ( len ( ans ) ) NEW_LINE for i in ans : NEW_LINE INDENT print ( i [ 0 ] , i [ 1 ] , i [ 2 ] ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 0 , 3 , 2 , 4 , 1 ] NEW_LINE n = 4 NEW_LINE sortPermutation ( arr , n ) NEW_LINE DEDENT