Maximize count of corresponding same elements in given permutations using cyclic rotations | C ++ program for the above approach ; Function to maximize the matching pairs between two permutation using left and right rotation ; Left array store distance of element from left side and right array store distance of element from right side ; Map to store index of elements ; idx1 is index of element in first permutation idx2 is index of element in second permutation ; If element if present on same index on both permutations then distance is zero ; Calculate distance from left and right side ; Calculate distance from left and right side ; Maps to store frequencies of elements present in left and right arrays ; Find maximum frequency ; Return the result ; Driver Code ; Given permutations P1 and P2 ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumMatchingPairs ( int perm1 [ ] , int perm2 [ ] , int n ) { int left [ n ] , right [ n ] ; map < int , int > mp1 , mp2 ; for ( int i = 0 ; i < n ; i ++ ) { mp1 [ perm1 [ i ] ] = i ; } for ( int j = 0 ; j < n ; j ++ ) { mp2 [ perm2 [ j ] ] = j ; } for ( int i = 0 ; i < n ; i ++ ) { int idx2 = mp2 [ perm1 [ i ] ] ; int idx1 = i ; if ( idx1 == idx2 ) { left [ i ] = 0 ; right [ i ] = 0 ; } else if ( idx1 < idx2 ) { left [ i ] = ( n - ( idx2 - idx1 ) ) ; right [ i ] = ( idx2 - idx1 ) ; } else { left [ i ] = ( idx1 - idx2 ) ; right [ i ] = ( n - ( idx1 - idx2 ) ) ; } } map < int , int > freq1 , freq2 ; for ( int i = 0 ; i < n ; i ++ ) { freq1 [ left [ i ] ] ++ ; freq2 [ right [ i ] ] ++ ; } int ans = 0 ; for ( int i = 0 ; i < n ; i ++ ) { ans = max ( ans , max ( freq1 [ left [ i ] ] , freq2 [ right [ i ] ] ) ) ; } return ans ; } int main ( ) { int P1 [ ] = { 5 , 4 , 3 , 2 , 1 } ; int P2 [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n = sizeof ( P1 ) / sizeof ( P1 [ 0 ] ) ; cout << maximumMatchingPairs ( P1 , P2 , n ) ; return 0 ; }