Number of Transpositions in a Permutation
Permutation A permutation is an arrangement of elements. A permutation of n elements can be represented by an arrangement of the numbers 1, 2, …n in some order. Eg. 5, 1, 4, 2, 3.
Cycle notation A permutation can be represented as a composition of permutation cycles. A permutation cycle is a set of elements in a permutation that trade places with one another.
For e.g.
P = { 5, 1, 4, 2, 3 }: Here, 5 goes to 1, 1 goes to 2 and so on (according to their indices position): 5 -> 1 1 -> 2 2 -> 4 4 -> 3 3 -> 5 Thus it can be represented as a single cycle: (5, 1, 2, 4, 3). Now consider the permutation: {5, 1, 4, 3, 2}. Here 5 -> 1 1 -> 2 2 -> 5 this closes 1 cycle. The other cycle is 4 -> 3 3 -> 4 In cycle notation it will be represented as (5, 1, 2) (4, 3).
Transpositions:
Now all cycles can be decomposed into a composition of 2 cycles (transpositions). The number of transpositions in a permutation is important as it gives the minimum number of 2 element swaps required to get this particular arrangement from the identity arrangement: 1, 2, 3, … n. The parity of the number of such 2 cycles represents whether the permutation is even or odd.
For e.g.
The cycle (5, 1, 2, 4, 3) can be written as (5, 3)(5, 4)(5, 2)(5, 1). 4 transpositions (even). Similarly, (5, 1, 2) -> (5, 2)(5, 1) (5, 1, 2)(4, 3) -> (5, 2)(5, 1)(4, 3). 3 transpositions (odd). It is clear from the examples that the number of transpositions from a cycle = length of the cycle - 1.
Problem
Given a permutation of n numbers P1, P2, P3, … Pn. Calculate the number of transpositions in it.
Example:
Input: 5 1 4 3 2 Output: 3
Approach:
The permutation can be easily represented as a directed graph where the number of connected components gives the number of cycles. And (the size of each component – 1) gives the number of transpositions from that cycle.
Example Permutation : {5, 1, 4, 3, 2} -> (5, 1, 2)(4, 3)
Below is the implementation of the above approach.
C++
// CPP Program to find the number of // transpositions in a permutation #include <bits/stdc++.h> using namespace std; #define N 1000001 int visited[N]; // This array stores which element goes to which position int goesTo[N]; // For eg. in { 5, 1, 4, 3, 2 } // goesTo[1] = 2 // goesTo[2] = 5 // goesTo[3] = 4 // goesTo[4] = 3 // goesTo[5] = 1 // This function returns the size of a component cycle int dfs( int i) { // If it is already visited if (visited[i] == 1) return 0; visited[i] = 1; int x = dfs(goesTo[i]); return (x + 1); } // This function returns the number // of transpositions in the permutation int noOfTranspositions( int P[], int n) { // Initializing visited[] array for ( int i = 1; i <= n; i++) visited[i] = 0; // building the goesTo[] array 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; } // Driver Code int main() { int permutation[] = { 5, 1, 4, 3, 2 }; int n = sizeof (permutation) / sizeof (permutation[0]); cout << noOfTranspositions(permutation, n); return 0; } |
Java
// Java Program to find the number of // transpositions in a permutation import java.io.*; class GFG { static int N = 1000001 ; static int visited[] = new int [N]; // This array stores which element // goes to which position static int goesTo[]= new int [N]; // For eg. in { 5, 1, 4, 3, 2 } // goesTo[1] = 2 // goesTo[2] = 5 // goesTo[3] = 4 // goesTo[4] = 3 // goesTo[5] = 1 // This function returns the size // of a component cycle static int dfs( int i) { // If it is already visited if (visited[i] == 1 ) return 0 ; visited[i] = 1 ; int x = dfs(goesTo[i]); return (x + 1 ); } // This function returns the number // of transpositions in the // permutation static int noOfTranspositions( int P[], int n) { // Initializing visited[] array for ( int i = 1 ; i <= n; i++) visited[i] = 0 ; // building the goesTo[] array 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; } // Driver Code public static void main (String[] args) { int permutation[] = { 5 , 1 , 4 , 3 , 2 }; int n = permutation.length ; System.out.println( noOfTranspositions(permutation, n)); } } // This code is contributed by anuj_67. |
Python3
# Python Program to find the number of # transpositions in a permutation N = 1000001 visited = [ 0 ] * N; # This array stores which element goes to which position goesTo = [ 0 ] * N; # For eg. in { 5, 1, 4, 3, 2 } # goesTo[1] = 2 # goesTo[2] = 5 # goesTo[3] = 4 # goesTo[4] = 3 # goesTo[5] = 1 # This function returns the size of a component cycle def dfs(i) : # If it is already visited if (visited[i] = = 1 ) : return 0 ; visited[i] = 1 ; x = dfs(goesTo[i]); return (x + 1 ); # This function returns the number # of transpositions in the permutation def noOfTranspositions(P, n) : # Initializing visited[] array for i in range ( 1 , n + 1 ) : visited[i] = 0 ; # building the goesTo[] array for i in range (n) : goesTo[P[i]] = i + 1 ; transpositions = 0 ; for i in range ( 1 , n + 1 ) : if (visited[i] = = 0 ) : ans = dfs(i); transpositions + = ans - 1 ; return transpositions; # Driver Code if __name__ = = "__main__" : permutation = [ 5 , 1 , 4 , 3 , 2 ]; n = len (permutation); print (noOfTranspositions(permutation, n)); # This code is contributed by AnkitRai01 |
C#
// C# Program to find the number of // transpositions in a permutation using System; class GFG { static int N = 1000001; static int []visited = new int [N]; // This array stores which element // goes to which position static int []goesTo= new int [N]; // For eg. in { 5, 1, 4, 3, 2 } // goesTo[1] = 2 // goesTo[2] = 5 // goesTo[3] = 4 // goesTo[4] = 3 // goesTo[5] = 1 // This function returns the size // of a component cycle static int dfs( int i) { // If it is already visited if (visited[i] == 1) return 0; visited[i] = 1; int x = dfs(goesTo[i]); return (x + 1); } // This function returns the number // of transpositions in the // permutation static int noOfTranspositions( int []P, int n) { // Initializing visited[] array for ( int i = 1; i <= n; i++) visited[i] = 0; // building the goesTo[] array 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; } // Driver Code public static void Main () { int []permutation = { 5, 1, 4, 3, 2 }; int n = permutation.Length ; Console.WriteLine( noOfTranspositions(permutation, n)); } } // This code is contributed by anuj_67. |
Javascript
<script> // Javascript Program to find the number of // transpositions in a permutation let N = 1000001 var visited = new Array(N); // This array stores which element goes to which position var goesTo = new Array(N); // For eg. in { 5, 1, 4, 3, 2 } // goesTo[1] = 2 // goesTo[2] = 5 // goesTo[3] = 4 // goesTo[4] = 3 // goesTo[5] = 1 // This function returns the size of a component cycle function dfs( i) { // If it is already visited if (visited[i] == 1) return 0; visited[i] = 1; let x = dfs(goesTo[i]); return (x + 1); } // This function returns the number // of transpositions in the permutation function noOfTranspositions( P, n) { // Initializing visited[] array for (let i = 1; i <= n; i++) visited[i] = 0; // building the goesTo[] array 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; } // Driver Code let permutation = [ 5, 1, 4, 3, 2 ]; let n = permutation.length; document.write(noOfTranspositions(permutation, n)); </script> |
3
Complexity Analysis:
- Time Complexity : O(n)
- Auxiliary space : O(n)