Number of Transpositions in a Permutation | Python Program to find the number of transpositions in a permutation ; This array stores which element goes to which position ; This function returns the size of a component cycle ; If it is already visited ; This functio returns the number of transpositions in the permutation ; Initializing visited [ ] array ; building the goesTo [ ] array ; Driver Code
N = 1000001 NEW_LINE visited = [ 0 ] * N ; NEW_LINE goesTo = [ 0 ] * N ; NEW_LINE def dfs ( i ) : NEW_LINE INDENT if ( visited [ i ] == 1 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT visited [ i ] = 1 ; NEW_LINE x = dfs ( goesTo [ i ] ) ; NEW_LINE return ( x + 1 ) ; NEW_LINE DEDENT def noOfTranspositions ( P , n ) : NEW_LINE INDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT visited [ i ] = 0 ; NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT goesTo [ P [ i ] ] = i + 1 ; NEW_LINE DEDENT transpositions = 0 ; NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( visited [ i ] == 0 ) : NEW_LINE INDENT ans = dfs ( i ) ; NEW_LINE transpositions += ans - 1 ; NEW_LINE DEDENT DEDENT return transpositions ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT permutation = [ 5 , 1 , 4 , 3 , 2 ] ; NEW_LINE n = len ( permutation ) ; NEW_LINE print ( noOfTranspositions ( permutation , n ) ) ; NEW_LINE DEDENT