Number of Transpositions in a Permutation | Javascript 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
let N = 1000001 var visited = new Array ( N ) ; var goesTo = new Array ( N ) ; function dfs ( i ) { if ( visited [ i ] == 1 ) return 0 ; visited [ i ] = 1 ; let x = dfs ( goesTo [ i ] ) ; return ( x + 1 ) ; } function noOfTranspositions ( P , n ) { for ( let i = 1 ; i <= n ; i ++ ) visited [ i ] = 0 ; for ( let i = 0 ; i < n ; i ++ ) goesTo [ P [ i ] ] = i + 1 ; let transpositions = 0 ; for ( let i = 1 ; i <= n ; i ++ ) { if ( visited [ i ] == 0 ) { let ans = dfs ( i ) ; transpositions += ans - 1 ; } } return transpositions ; } let permutation = [ 5 , 1 , 4 , 3 , 2 ] ; let n = permutation . length ; document . write ( noOfTranspositions ( permutation , n ) ) ;