Permutación Una permutación es un arreglo de elementos. Una permutación de n elementos se puede representar mediante una disposición de los números 1, 2, … n en algún orden. P.ej. 5, 1, 4, 2, 3.
Notación de ciclo Una permutación se puede representar como una composición de ciclos de permutación. Un ciclo de permutación es un conjunto de elementos en una permutación que intercambian lugares entre sí.
Por ejemplo
P = { 5, 1, 4, 2, 3 }:
Aquí, 5 va a 1, 1 va a 2 y así sucesivamente (según la posición de sus índices):
5 -> 1
1 -> 2
2 -> 4
4 – > 3
3 -> 5
Así se puede representar como un solo ciclo: (5, 1, 2, 4, 3).
Ahora considera la permutación: {5, 1, 4, 3, 2}. Aquí
5 -> 1
1 -> 2
2 -> 5 esto cierra 1 ciclo.
El otro ciclo es
4 -> 3
3 -> 4
En notación de ciclo se representará como (5, 1, 2) (4, 3).
Transposiciones
Ahora todos los ciclos se pueden descomponer en una composición de 2 ciclos (transposiciones). El número de transposiciones en una permutación es importante ya que proporciona el número mínimo de intercambios de 2 elementos necesarios para obtener este arreglo particular del arreglo de identidad: 1, 2, 3, … n. La paridad del número de tales 2 ciclos representa si la permutación es par o impar.
Por ejemplo
El ciclo (5, 1, 2, 4, 3) se puede escribir como (5, 3)(5, 4)(5, 2)(5, 1). 4 transposiciones (pares).
Del mismo modo,
(5, 1, 2) -> (5, 2)(5, 1)
(5, 1, 2)(4, 3) -> (5, 2)(5, 1)(4, 3) . 3 transposiciones (impares).
Está claro a partir de los ejemplos que el número de transposiciones de un ciclo = duración del ciclo – 1.
Problema
Dada una permutación de n números P 1 , P 2 , P 3 , … P n . Calcular el número de transposiciones en él.
Ejemplo:
Input: 5 1 4 3 2 Output: 3
Enfoque : la permutación se puede representar fácilmente como un gráfico dirigido donde el número de componentes conectados da el número de ciclos. Y (el tamaño de cada componente – 1) da el número de transposiciones de ese ciclo.
Ejemplo de permutación : {5, 1, 4, 3, 2} -> (5, 1, 2)(4, 3)
A continuación se muestra la implementación del enfoque anterior.
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>
Producción:
3
Tiempo Complejidad : O(n)
Espacio auxiliar : O(n)
Publicación traducida automáticamente
Artículo escrito por narutouzumaki696 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA