Minimum number of swaps required for arranging pairs adjacent to each other | This function updates indexes of elements ' a ' and 'b   ; This function returns minimum number of swaps required to arrange all elements of arr [ i . . n ] become arranged ; If all pairs procesed so no swapping needed return 0 ; If current pair is valid so DO NOT DISTURB this pair and move ahead . ; Swap pair of arr [ i ] with arr [ i + 1 ] and recursively compute minimum swap required if this move is made . ; Backtrack to previous configuration . Also restore the previous indices , of one and two ; Now swap arr [ i ] with pair of arr [ i + 1 ] and recursively compute minimum swaps required for the subproblem after this move ; Backtrack to previous configuration . Also restore 3 the previous indices , of one and two ; Return minimum of two cases ; Returns minimum swaps required ; To store indices of array elements ; Store index of each element in array index ; Call the recursive function ; For simplicity , it is assumed that arr [ 0 ] is not used . The elements from index 1 to n are only valid elements ; if ( a , b ) is pair than we have assigned elements in array such that pairs [ a ] = b and pairs [ b ] = a ; Number of pairs n is half of total elements ; If there are n elements in array , then there are n pairs
def updateindex ( index , a , ai , b , bi ) : NEW_LINE INDENT index [ a ] = ai NEW_LINE index [ b ] = bi NEW_LINE DEDENT def minSwapsUtil ( arr , pairs , index , i , n ) : NEW_LINE INDENT if ( i > n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( pairs [ arr [ i ] ] == arr [ i + 1 ] ) : NEW_LINE INDENT return minSwapsUtil ( arr , pairs , index , i + 2 , n ) NEW_LINE DEDENT one = arr [ i + 1 ] NEW_LINE indextwo = i + 1 NEW_LINE indexone = index [ pairs [ arr [ i ] ] ] NEW_LINE two = arr [ index [ pairs [ arr [ i ] ] ] ] NEW_LINE arr [ i + 1 ] , arr [ indexone ] = arr [ indexone ] , arr [ i + 1 ] NEW_LINE updateindex ( index , one , indexone , two , indextwo ) NEW_LINE a = minSwapsUtil ( arr , pairs , index , i + 2 , n ) NEW_LINE arr [ i + 1 ] , arr [ indexone ] = arr [ indexone ] , arr [ i + 1 ] NEW_LINE updateindex ( index , one , indextwo , two , indexone ) NEW_LINE one = arr [ i ] NEW_LINE indexone = index [ pairs [ arr [ i + 1 ] ] ] NEW_LINE two = arr [ index [ pairs [ arr [ i + 1 ] ] ] ] NEW_LINE indextwo = i NEW_LINE arr [ i ] , arr [ indexone ] = arr [ indexone ] , arr [ i ] NEW_LINE updateindex ( index , one , indexone , two , indextwo ) NEW_LINE b = minSwapsUtil ( arr , pairs , index , i + 2 , n ) NEW_LINE arr [ i ] , arr [ indexone ] = arr [ indexone ] , arr [ i ] NEW_LINE updateindex ( index , one , indextwo , two , indexone ) NEW_LINE return 1 + min ( a , b ) NEW_LINE DEDENT def minSwaps ( n , pairs , arr ) : NEW_LINE INDENT index = [ ] NEW_LINE for i in range ( 2 * n + 1 + 1 ) : NEW_LINE INDENT index . append ( 0 ) NEW_LINE DEDENT for i in range ( 1 , 2 * n + 1 ) : NEW_LINE INDENT index [ arr [ i ] ] = i NEW_LINE DEDENT return minSwapsUtil ( arr , pairs , index , 1 , 2 * n ) NEW_LINE DEDENT arr = [ 0 , 3 , 5 , 6 , 4 , 1 , 2 ] NEW_LINE pairs = [ 0 , 3 , 6 , 1 , 5 , 4 , 2 ] NEW_LINE m = len ( pairs ) NEW_LINE n = m // 2 NEW_LINE print ( " Min ▁ swaps ▁ required ▁ is ▁ " , minSwaps ( n , pairs , arr ) ) NEW_LINE