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.
|
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.
