Una permutación es un reordenamiento de miembros de una secuencia en una nueva secuencia. Por ejemplo, hay 24 permutaciones de [a, b, c, d] . Algunos de ellos son [b, a, d, c] , [d, a, b, c] y [a, d, b, c] .
Una permutación se puede especificar mediante una array P[] donde P[i] representa la ubicación del elemento en el índice i en la permutación.
Por ejemplo, la array [3, 2, 1, 0] representa la permutación que asigna el elemento del índice 0 al índice 3, el elemento del índice 1 al índice 2, el elemento del índice 2 al índice 1 y el elemento del índice 3 al índice 0.
Dada la array arr[] deN elementos y una array de permutación P[] , la tarea es permutar la array dada arr[] en función de la array de permutación P[] .
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}, P[] = {3, 2, 1, 0}
Salida: 4 3 2 1
Entrada: arr[] = {11, 32, 3, 42} , P[] = {2, 3, 0, 1}
Salida: 3 42 11 32
Enfoque: cada permutación se puede representar mediante una colección de permutaciones independientes, cada una de las cuales es cíclica, es decir, mueve todos los elementos mediante un ajuste de desplazamiento fijo. Para encontrar y aplicar el ciclo que indica la entrada i , siga avanzando (de i a P[i] ) hasta que regresemos a i . Después de completar el ciclo actual, busque otro ciclo que aún no se haya aplicado. Para verificar esto, reste n de P[i] después de aplicarlo. Esto significa que si una entrada en P[i] es negativa, hemos realizado el movimiento correspondiente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to permute the given
// array based on the given conditions
int permute(int A[], int P[], int n)
{
// For each element of P
for (int i = 0; i < n; i++) {
int next = i;
// Check if it is already
// considered in cycle
while (P[next] >= 0) {
// Swap the current element according
// to the permutation in P
swap(A[i], A[P[next]]);
int temp = P[next];
// Subtract n from an entry in P
// to make it negative which indicates
// the corresponding move
// has been performed
P[next] -= n;
next = temp;
}
}
}
// Driver code
int main()
{
int A[] = { 5, 6, 7, 8 };
int P[] = { 3, 2, 1, 0 };
int n = sizeof(A) / sizeof(int);
permute(A, P, n);
// Print the new array after
// applying the permutation
for (int i = 0; i < n; i++)
cout << A[i] << " ";
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to permute the given
// array based on the given conditions
static void permute(int A[], int P[], int n)
{
// For each element of P
for (int i = 0; i < n; i++)
{
int next = i;
// Check if it is already
// considered in cycle
while (P[next] >= 0)
{
// Swap the current element according
// to the permutation in P
swap(A, i, P[next]);
int temp = P[next];
// Subtract n from an entry in P
// to make it negative which indicates
// the corresponding move
// has been performed
P[next] -= n;
next = temp;
}
}
}
static int[] swap(int []arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver code
public static void main(String[] args)
{
int A[] = { 5, 6, 7, 8 };
int P[] = { 3, 2, 1, 0 };
int n = A.length;
permute(A, P, n);
// Print the new array after
// applying the permutation
for (int i = 0; i < n; i++)
System.out.print(A[i]+ " ");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 implementation of the approach # Function to permute the given # array based on the given conditions def permute(A, P, n): # For each element of P for i in range(n): next = i # Check if it is already # considered in cycle while (P[next] >= 0): # Swap the current element according # to the permutation in P t = A[i] A[i] = A[P[next]] A[P[next]] = t temp = P[next] # Subtract n from an entry in P # to make it negative which indicates # the corresponding move # has been performed P[next] -= n next = temp # Driver code if __name__ == '__main__': A = [5, 6, 7, 8] P = [3, 2, 1, 0] n = len(A) permute(A, P, n) # Print the new array after # applying the permutation for i in range(n): print(A[i], end = " ") # This code is contributed by Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to permute the given
// array based on the given conditions
static void permute(int []A, int []P, int n)
{
// For each element of P
for (int i = 0; i < n; i++)
{
int next = i;
// Check if it is already
// considered in cycle
while (P[next] >= 0)
{
// Swap the current element according
// to the permutation in P
swap(A, i, P[next]);
int temp = P[next];
// Subtract n from an entry in P
// to make it negative which indicates
// the corresponding move
// has been performed
P[next] -= n;
next = temp;
}
}
}
static int[] swap(int []arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver code
public static void Main()
{
int []A = { 5, 6, 7, 8 };
int []P = { 3, 2, 1, 0 };
int n = A.Length;
permute(A, P, n);
// Print the new array after
// applying the permutation
for (int i = 0; i < n; i++)
Console.Write(A[i]+ " ");
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript implementation of the approach
// Function to permute the given
// array based on the given conditions
function permute(A, P, n) {
// For each element of P
for (let i = 0; i < n; i++) {
let next = i;
// Check if it is already
// considered in cycle
while (P[next] >= 0) {
// Swap the current element according
// to the permutation in P
let x = A[i];
A[i] = A[P[next]];
A[P[next]] = x;
let temp = P[next];
// Subtract n from an entry in P
// to make it negative which indicates
// the corresponding move
// has been performed
P[next] -= n;
next = temp;
}
}
}
// Driver code
let A = [5, 6, 7, 8];
let P = [3, 2, 1, 0];
let n = A.length;
permute(A, P, n);
// Print the new array after
// applying the permutation
for (let i = 0; i < n; i++)
document.write(A[i] + " ");
</script>
8 7 6 5
Complejidad de tiempo: O(n)
Complejidad de espacio: O(1)