We are going to share a **CPP Program to find the number of transpositions in a permutation**. If you are a beginner and want to start learning the C++ programming, then keep your close attention in this tutorial as I am going to share a program for CPP Program to **find the number of transpositions in a permutation** with the output.

Copy the below C++ program and execute it with the help of GCC compiler. At the end of this program, We have shared the output of this program.

C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <bits/stdc++.h> using namespace std; #define N 1000001 int visited[N]; int goesTo[N]; int dfs(int i) { if (visited[i] == 1) return 0; visited[i] = 1; int x = dfs(goesTo[i]); return (x + 1); } 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; } int main() { int permutation[] = { 5, 1, 4, 3, 2 }; int n = sizeof(permutation) / sizeof(permutation[0]); cout << noOfTranspositions(permutation, n); return 0; } |

3

If you like FreeWebMentor and you would like to contribute, you can write an article and mail your article to [email protected] Your article will appear on the FreeWebMentor main page and help other developers.

- C++ program to reverse a single linked list
- c++ program to remove vowels from a string
- CPP program to check if a number is Wagstaff prime or not
- CPP program to remove punctuation from a given string
- C++ program to find minimum players required to win the game anyhow
- C++ program to print primes smaller than n using Sieve of Sundaram
- C++ program to find count of divisors in n!
- C++ implementation to sort the given matrix
- C++ program to find Majority element in an array
- How to convert a string to integer array in CPP