Number of Transpositions in a Permutation | Java 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
import java . io . * ; class GFG { static int N = 1000001 ; static int visited [ ] = new int [ N ] ; static int goesTo [ ] = new int [ N ] ; static int dfs ( int i ) { if ( visited [ i ] == 1 ) return 0 ; visited [ i ] = 1 ; int x = dfs ( goesTo [ i ] ) ; return ( x + 1 ) ; } static int noOfTranspositions ( int P [ ] , int n ) { for ( int i = 1 ; i <= n ; i ++ ) visited [ i ] = 0 ; for ( int i = 0 ; i < n ; i ++ ) goesTo [ P [ i ] ] = i + 1 ; int transpositions = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { if ( visited [ i ] == 0 ) { int ans = dfs ( i ) ; transpositions += ans - 1 ; } } return transpositions ; } public static void main ( String [ ] args ) { int permutation [ ] = { 5 , 1 , 4 , 3 , 2 } ; int n = permutation . length ; System . out . println ( noOfTranspositions ( permutation , n ) ) ; } }