Maximize count of corresponding same elements in given permutations using cyclic rotations | Python3 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
from collections import defaultdict NEW_LINE def maximumMatchingPairs ( perm1 , perm2 , n ) : NEW_LINE INDENT left = [ 0 ] * n NEW_LINE right = [ 0 ] * n NEW_LINE mp1 = { } NEW_LINE mp2 = { } NEW_LINE for i in range ( n ) : NEW_LINE INDENT mp1 [ perm1 [ i ] ] = i NEW_LINE DEDENT for j in range ( n ) : NEW_LINE INDENT mp2 [ perm2 [ j ] ] = j NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT idx2 = mp2 [ perm1 [ i ] ] NEW_LINE idx1 = i NEW_LINE if ( idx1 == idx2 ) : NEW_LINE INDENT left [ i ] = 0 NEW_LINE right [ i ] = 0 NEW_LINE DEDENT elif ( idx1 < idx2 ) : NEW_LINE INDENT left [ i ] = ( n - ( idx2 - idx1 ) ) NEW_LINE right [ i ] = ( idx2 - idx1 ) NEW_LINE DEDENT else : NEW_LINE INDENT left [ i ] = ( idx1 - idx2 ) NEW_LINE right [ i ] = ( n - ( idx1 - idx2 ) ) NEW_LINE DEDENT DEDENT freq1 = defaultdict ( int ) NEW_LINE freq2 = defaultdict ( int ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT freq1 [ left [ i ] ] += 1 NEW_LINE freq2 [ right [ i ] ] += 1 NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT ans = max ( ans , max ( freq1 [ left [ i ] ] , freq2 [ right [ i ] ] ) ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT P1 = [ 5 , 4 , 3 , 2 , 1 ] NEW_LINE P2 = [ 1 , 2 , 3 , 4 , 5 ] NEW_LINE n = len ( P1 ) NEW_LINE print ( maximumMatchingPairs ( P1 , P2 , n ) ) NEW_LINE DEDENT