Sort a string lexicographically using triple cyclic shifts | Python3 program for sorting a string using cyclic shift of three indices ; Store the indices which haven 't attained  its correct position ; Store the indices undergoing cyclic shifts ; If the element is not at it 's correct position ; Check if all 3 indices can be placed to respective correct indices in a single move ; If the i - th index is still not present in its correct position , store the index ; To check if swapping two indices places them in their correct position ; for i in range len ( indices ) : print ( indices [ i ] [ 0 ] , indices [ i ] [ 1 ] , indices [ i ] [ 2 ] ) ; Driver code
import math NEW_LINE def sortString ( arr , n , moves ) : NEW_LINE INDENT pos = [ ] NEW_LINE indices = [ ] NEW_LINE flag = False NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] != i ) : NEW_LINE INDENT if ( arr [ arr [ arr [ i ] ] ] == i and arr [ arr [ i ] ] != i ) : NEW_LINE INDENT temp = arr [ arr [ i ] ] NEW_LINE indices . append ( [ i , arr [ i ] , arr [ arr [ i ] ] ] ) NEW_LINE sw = arr [ i ] NEW_LINE arr [ i ] = arr [ arr [ i ] ] NEW_LINE arr [ sw ] = sw NEW_LINE sw = arr [ i ] NEW_LINE arr [ i ] = arr [ temp ] NEW_LINE arr [ temp ] = sw NEW_LINE DEDENT DEDENT if ( arr [ i ] != i ) : NEW_LINE INDENT pos . append ( i ) NEW_LINE DEDENT DEDENT for i in range ( n ) : NEW_LINE INDENT if ( arr [ i ] != i ) : NEW_LINE INDENT pos1 = i NEW_LINE pos2 = arr [ i ] NEW_LINE pos3 = arr [ arr [ i ] ] NEW_LINE if ( pos3 != pos1 ) : NEW_LINE INDENT indices . append ( [ pos1 , pos2 , pos3 ] ) NEW_LINE arr [ pos1 ] , arr [ pos2 ] = arr [ pos2 ] , arr [ pos1 ] NEW_LINE arr [ pos1 ] , arr [ pos3 ] = arr [ pos3 ] , arr [ pos1 ] NEW_LINE pos . remove ( pos2 ) NEW_LINE if pos3 in pos : NEW_LINE INDENT pos . remove ( pos3 ) NEW_LINE DEDENT if ( arr [ pos1 ] == pos1 ) : NEW_LINE INDENT pos . remove ( pos1 ) NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( pos3 == pos [ 0 ] ) : NEW_LINE INDENT it = 0 NEW_LINE if ( pos [ 0 ] != pos [ - 1 ] ) : NEW_LINE INDENT it = it + 1 NEW_LINE pos3 = pos [ it ] NEW_LINE if ( pos [ it ] != pos [ - 1 ] and pos3 == pos2 ) : NEW_LINE INDENT it = it + 1 NEW_LINE pos3 = pos [ it ] NEW_LINE DEDENT elif ( pos [ it ] == pos [ - 1 ] and pos3 == pos2 ) : NEW_LINE INDENT flag = True NEW_LINE break NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT flag = True NEW_LINE break NEW_LINE DEDENT DEDENT indices . append ( [ pos1 , pos2 , pos3 ] ) NEW_LINE arr [ pos1 ] , arr [ pos2 ] = arr [ pos2 ] , arr [ pos1 ] NEW_LINE arr [ pos1 ] , arr [ pos3 ] = arr [ pos3 ] , arr [ pos1 ] NEW_LINE pos . remove ( pos2 ) NEW_LINE DEDENT DEDENT if ( arr [ i ] != i ) : NEW_LINE INDENT i = i - 1 NEW_LINE DEDENT DEDENT if ( flag == True or len ( indices ) > moves ) : NEW_LINE INDENT print ( " Not ▁ Possible " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( len ( indices ) ) NEW_LINE DEDENT DEDENT s = " adceb " NEW_LINE arr = [ ] NEW_LINE for i in s : NEW_LINE INDENT arr . append ( ord ( i ) - ord ( ' a ' ) ) NEW_LINE DEDENT sortString ( arr , len ( s ) , math . floor ( len ( s ) / 2 ) ) NEW_LINE