Dada una array de tamaño n de números enteros en el rango de 1 a n, necesitamos encontrar la permutación inversa de esa array.
Una permutación inversa es una permutación que obtendrá al insertar la posición de un elemento en la posición especificada por el valor del elemento en la array. Para una mejor comprensión, considere el siguiente ejemplo:
supongamos que encontramos el elemento 4 en la posición 3 en una array, luego, en permutación inversa, insertamos 3 (posición del elemento 4 en la array) en la posición 4 (valor del elemento).
Básicamente, una permutación inversa es una permutación en la que se intercambia cada número y el número del lugar que ocupa.
La array debe contener elementos desde 1 hasta array_size.
Ejemplo 1 :
Input = {1, 4, 3, 2}
Output = {1, 4, 3, 2}
En esto, para el elemento 1, insertamos la posición 1 desde arr1, es decir, 1 en la posición 1 en arr2. Para el elemento 4 en arr1, insertamos 2 desde arr1 en la posición 4 en arr2. De manera similar, para el elemento 2 en arr1, insertamos la posición de 2, es decir, 4 en arr2.
Example 2 :
Input = {2, 3, 4, 5, 1}
Output = {5, 1, 2, 3, 4}
En este ejemplo, para el elemento 2 insertamos la posición de 2 desde arr1 en arr2 en la posición 2. De manera similar, encontramos la permutación inversa de otros elementos.
Considere una array arr que tiene los elementos 1 a n.
Método 1:
en este método, tomamos los elementos uno por uno y verificamos los elementos en orden creciente e imprimimos la posición del elemento donde encontramos ese elemento.
C++
// Naive CPP Program to find inverse permutation.
#include <bits/stdc++.h>
using namespace std;
// C++ function to find inverse permutations
void inversePermutation(int arr[], int size) {
// Loop to select Elements one by one
for (int i = 0; i < size; i++) {
// Loop to print position of element
// where we find an element
for (int j = 0; j < size; j++) {
// checking the element in increasing order
if (arr[j] == i + 1) {
// print position of element where
// element is in inverse permutation
cout << j + 1 << " ";
break;
}
}
}
}
// Driver program to test above function
int main() {
int arr[] = {2, 3, 4, 5, 1};
int size = sizeof(arr) / sizeof(arr[0]);
inversePermutation(arr, size);
return 0;
}
Java
// Naive java Program to find inverse permutation.
import java.io.*;
class GFG {
// java function to find inverse permutations
static void inversePermutation(int arr[], int size)
{
int i ,j;
// Loop to select Elements one by one
for ( i = 0; i < size; i++)
{
// Loop to print position of element
// where we find an element
for ( j = 0; j < size; j++)
{
// checking the element in
// increasing order
if (arr[j] == i + 1)
{
// print position of element
// where element is in inverse
// permutation
System.out.print( j + 1 + " ");
break;
}
}
}
}
// Driver program to test above function
public static void main (String[] args)
{
int arr[] = {2, 3, 4, 5, 1};
int size = arr.length;
inversePermutation(arr, size);
}
}
// This code is contributed by vt_m
Python3
# Naive Python3 Program to # find inverse permutation. # Function to find inverse permutations def inversePermutation(arr, size): # Loop to select Elements one by one for i in range(0, size): # Loop to print position of element # where we find an element for j in range(0, size): # checking the element in increasing order if (arr[j] == i + 1): # print position of element where # element is in inverse permutation print(j + 1, end = " ") break # Driver Code arr = [2, 3, 4, 5, 1] size = len(arr) inversePermutation(arr, size) #This code is contributed by Smitha Dinesh Semwal
C#
// Naive C# Program to find inverse permutation.
using System;
class GFG {
// java function to find inverse permutations
static void inversePermutation(int []arr, int size)
{
int i ,j;
// Loop to select Elements one by one
for ( i = 0; i < size; i++)
{
// Loop to print position of element
// where we find an element
for ( j = 0; j < size; j++)
{
// checking the element in
// increasing order
if (arr[j] == i + 1)
{
// print position of element
// where element is in inverse
// permutation
Console.Write( j + 1 + " ");
break;
}
}
}
}
// Driver program to test above function
public static void Main ()
{
int []arr = {2, 3, 4, 5, 1};
int size = arr.Length;
inversePermutation(arr, size);
}
}
// This code is contributed by vt_m
PHP
<?php
// Naive PHP Program to
// find inverse permutation.
// Function to find
// inverse permutations
function inversePermutation($arr, $size)
{
for ( $i = 0; $i < $size; $i++)
{
// Loop to print position of element
// where we find an element
for ($j = 0; $j < $size; $j++)
{
// checking the element
// in increasing order
if ($arr[$j] == $i + 1)
{
// print position of element
// where element is in
// inverse permutation
echo $j + 1 , " ";
break;
}
}
}
}
// Driver Code
$arr = array(2, 3, 4, 5, 1);
$size = sizeof($arr);
inversePermutation($arr, $size);
// This code is contributed by aj_36
?>
Javascript
<script>
// Naive JavaScript program to find inverse permutation.
// JavaScript function to find inverse permutations
function inversePermutation(arr, size)
{
let i ,j;
// Loop to select Elements one by one
for ( i = 0; i < size; i++)
{
// Loop to print position of element
// where we find an element
for ( j = 0; j < size; j++)
{
// checking the element in
// increasing order
if (arr[j] == i + 1)
{
// print position of element
// where element is in inverse
// permutation
document.write( j + 1 + " ");
break;
}
}
}
}
// Driver code
let arr = [2, 3, 4, 5, 1];
let size = arr.length;
inversePermutation(arr, size);
</script>
Producción :
5 1 2 3 4
Método 2:
la idea es usar otra array para almacenar asignaciones de índices y elementos
C++
// Efficient CPP Program to find inverse permutation.
#include <bits/stdc++.h>
using namespace std;
// C++ function to find inverse permutations
void inversePermutation(int arr[], int size) {
// to store element to index mappings
int arr2[size];
// Inserting position at their
// respective element in second array
for (int i = 0; i < size; i++)
arr2[arr[i] - 1] = i + 1;
for (int i = 0; i < size; i++)
cout << arr2[i] << " ";
}
// Driver program to test above function
int main() {
int arr[] = {2, 3, 4, 5, 1};
int size = sizeof(arr) / sizeof(arr[0]);
inversePermutation(arr, size);
return 0;
}
Java
// Efficient Java Program to find
// inverse permutation.
import java.io.*;
class GFG {
// function to find inverse permutations
static void inversePermutation(int arr[], int size) {
// to store element to index mappings
int arr2[] = new int[size];
// Inserting position at their
// respective element in second array
for (int i = 0; i < size; i++)
arr2[arr[i] - 1] = i + 1;
for (int i = 0; i < size; i++)
System.out.print(arr2[i] + " ");
}
// Driver program to test above function
public static void main(String args[]) {
int arr[] = {2, 3, 4, 5, 1};
int size = arr.length;
inversePermutation(arr, size);
}
}
// This code is contributed by Nikita Tiwari.
Python3
# Efficient Python 3 Program to find # inverse permutation. # function to find inverse permutations def inversePermutation(arr, size) : # To store element to index mappings arr2 = [0] *(size) # Inserting position at their # respective element in second array for i in range(0, size) : arr2[arr[i] - 1] = i + 1 for i in range(0, size) : print( arr2[i], end = " ") # Driver program arr = [2, 3, 4, 5, 1] size = len(arr) inversePermutation(arr, size) # This code is contributed by Nikita Tiwari.
C#
// Efficient C# Program to find
// inverse permutation.
using System;
class GFG {
// function to find inverse permutations
static void inversePermutation(int []arr, int size) {
// to store element to index mappings
int []arr2 = new int[size];
// Inserting position at their
// respective element in second array
for (int i = 0; i < size; i++)
arr2[arr[i] - 1] = i + 1;
for (int i = 0; i < size; i++)
Console.Write(arr2[i] + " ");
}
// Driver program to test above function
public static void Main() {
int []arr = {2, 3, 4, 5, 1};
int size = arr.Length;
inversePermutation(arr, size);
}
}
// This code is contributed by vt_m.
Output : 5 1 2 3 4
Publicación traducida automáticamente
Artículo escrito por rishabh1322 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA