Minimum number of swaps required for arranging pairs adjacent to each other | C ++ program to find minimum number of swaps required so that all pairs become adjacent . ; 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 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 ; Driver program ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void updateindex ( int index [ ] , int a , int ai , int b , int bi ) { index [ a ] = ai ; index [ b ] = bi ; } int minSwapsUtil ( int arr [ ] , int pairs [ ] , int index [ ] , int i , int n ) { if ( i > n ) return 0 ; if ( pairs [ arr [ i ] ] == arr [ i + 1 ] ) return minSwapsUtil ( arr , pairs , index , i + 2 , n ) ; int one = arr [ i + 1 ] ; int indextwo = i + 1 ; int indexone = index [ pairs [ arr [ i ] ] ] ; int two = arr [ index [ pairs [ arr [ i ] ] ] ] ; swap ( arr [ i + 1 ] , arr [ indexone ] ) ; updateindex ( index , one , indexone , two , indextwo ) ; int a = minSwapsUtil ( arr , pairs , index , i + 2 , n ) ; swap ( arr [ i + 1 ] , arr [ indexone ] ) ; updateindex ( index , one , indextwo , two , indexone ) ; one = arr [ i ] , indexone = index [ pairs [ arr [ i + 1 ] ] ] ; two = arr [ index [ pairs [ arr [ i + 1 ] ] ] ] , indextwo = i ; swap ( arr [ i ] , arr [ indexone ] ) ; updateindex ( index , one , indexone , two , indextwo ) ; int b = minSwapsUtil ( arr , pairs , index , i + 2 , n ) ; swap ( arr [ i ] , arr [ indexone ] ) ; updateindex ( index , one , indextwo , two , indexone ) ; return 1 + min ( a , b ) ; } int minSwaps ( int n , int pairs [ ] , int arr [ ] ) { int index [ 2 * n + 1 ] ; for ( int i = 1 ; i <= 2 * n ; i ++ ) index [ arr [ i ] ] = i ; return minSwapsUtil ( arr , pairs , index , 1 , 2 * n ) ; } int main ( ) { int arr [ ] = { 0 , 3 , 5 , 6 , 4 , 1 , 2 } ; int pairs [ ] = { 0 , 3 , 6 , 1 , 5 , 4 , 2 } ; int m = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int n = m / 2 ; cout << " Min ▁ swaps ▁ required ▁ is ▁ " << minSwaps ( n , pairs , arr ) ; return 0 ; }