Dada una permutación de los primeros N enteros positivos, la tarea es formar la permutación lexicográficamente más pequeña de manera que la nueva permutación no tenga ningún elemento que tenga el mismo índice que la anterior. Si es imposible hacer tal permutación, imprima -1.
Ejemplos :
Entrada : N = 5, arr[] = {1, 2, 3, 4, 5}
Salida : 2 1 4 5 3
Explicación : Es la permutación lexicográficamente más pequeña posible
siguiendo la condición de 0 a N – 1 tal que arr[ i] != b[i].Entrada : N = 1, arr[] = {1}
Salida : -1
Enfoque : para resolver el problema, siga la siguiente idea:
- Primero, cree la permutación lexicográficamente más pequeña y verifique si arr[i] es lo mismo que b[i]. Si no es el último elemento, cambie b[i] y b[i + 1].
- Si es el último elemento, intercambie b[i] y b[i – 1] porque no hay ningún elemento delante de b[i] ya que es el último elemento.
Siga los pasos a continuación para resolver el problema:
- Primero, cree un vector b de tamaño N de 1 a N.
- Ejecute un bucle en el vector b desde el índice 0 hasta N – 1.
- Si los elementos son diferentes entonces continúe.
- De lo contrario, si i no es N – 1, intercambia b[i] y b[i + 1]
- Si i no es 0 pero es el último elemento, intercambia b[i] y b[i – 1]
- De lo contrario, si es el único elemento, imprima -1.
- Después de ejecutar el bucle, imprima el vector b .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// Function to find lexicographically
// smallest permutation
void findPerm(int a[], int n)
{
// Declare a vector of size n
vector<ll> b(n);
// Copy the vector a to b
for (ll i = 0; i < n; i++) {
b[i] = i + 1;
}
for (ll i = 0; i < n; i++) {
// Elements are different
if (a[i] != b[i])
continue;
// Elements are same
if (i + 1 < n)
swap(b[i], b[i + 1]);
else if (i - 1 > 0)
swap(b[i], b[i - 1]);
else {
cout << -1 << endl;
return;
}
}
// Print the lexicographically
// smallest permutation
for (ll i = 0; i < n; i++)
cout << b[i] << " ";
cout << endl;
}
// Driver Code
int main()
{
int N = 5;
int arr[] = { 1, 2, 3, 4, 5 };
// Function call
findPerm(arr, N);
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find lexicographically
// smallest permutation
public static void findPerm(int a[], int n)
{
// Declare an array of size n
int b[] = new int[n];
// Copy the array a to b
for (int i = 0; i < n; i++) {
b[i] = i + 1;
}
for (int i = 0; i < n; i++) {
// Elements are different
if (a[i] != b[i])
continue;
// Elements are same
if (i + 1 < n) {
int temp = b[i];
b[i] = b[i + 1];
b[i + 1] = temp;
}
else if (i - 1 > 0) {
int temp = b[i];
b[i] = b[i - 1];
b[i - 1] = temp;
}
else {
System.out.println(-1);
return;
}
}
// Print the lexicographically
// smallest permutation
for (int i = 0; i < n; i++)
System.out.print(b[i] + " ");
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
int N = 5;
int arr[] = { 1, 2, 3, 4, 5 };
// Function call
findPerm(arr, N);
}
}
// This code is contributed by Rohit Pradhan
Python3
# pyton3 code to implement the above approach # Function to find lexicographically # smallest permutation def findPerm(a, n): # Declare a vector of size n b = [0 for _ in range(n)] # Copy the vector a to b for i in range(0, n): b[i] = i + 1 for i in range(0, n): # Elements are different if (a[i] != b[i]): continue # Elements are same if (i + 1 < n): temp = b[i] b[i] = b[i+1] b[i+1] = temp elif (i - 1 > 0): temp = b[i] b[i] = b[i-1] b[i-1] = temp else: print(-1) return # Print the lexicographically # smallest permutation for i in range(0, n): print(b[i], end=" ") print() # Driver Code if __name__ == "__main__": N = 5 arr = [1, 2, 3, 4, 5] # Function call findPerm(arr, N) # This code is contributed by rakeshsahni
C#
// C# code to implement the above approach
using System;
class GFG
{
// Driver Code
public static void Main(string[] args)
{
int N = 5;
int[] arr = { 1, 2, 3, 4, 5 };
// Function call
findPerm(arr, N);
}
// Function to find lexicographically
// smallest permutation
public static void findPerm(int[] a, int n)
{
// Declare an array of size n
int[] b = new int[n];
// Copy the array a to b
for (int i = 0; i < n; i++) {
b[i] = i + 1;
}
for (int i = 0; i < n; i++) {
// Elements are different
if (a[i] != b[i])
continue;
// Elements are same
if (i + 1 < n) {
int temp = b[i];
b[i] = b[i + 1];
b[i + 1] = temp;
}
else if (i - 1 > 0) {
int temp = b[i];
b[i] = b[i - 1];
b[i - 1] = temp;
}
else {
Console.WriteLine(-1);
return;
}
}
// Print the lexicographically
// smallest permutation
for (int i = 0; i < n; i++)
Console.Write(b[i] + " ");
Console.WriteLine();
}
}
// This code is contributed by Tapesh(tapeshdua420)
Javascript
<script>
// Function to find lexicographically
// smallest permutation
function swat(a, b)
{
// create a temporary variable
a = a + b;
b = a - b;
a = a - b;
}
function findPerm(a, n)
{
// Declare a array of size n
let b=new Array(n);
// Copy the vector a to b
for (let i = 0; i < n; i++) {
b[i] = i + 1;
}
for (let i = 0; i < n; i++) {
// Elements are different
if (a[i] != b[i])
continue;
// Elements are same
if (i + 1 < n)
swat(b[i], b[i + 1]);
else if (i - 1 > 0)
swat(b[i], b[i - 1]);
else {
document.write(-1);
document.write( "<br>");
return;
}
}
// Print the lexicographically
// smallest permutation
for (let i = 0; i < n; i++)
document.write(b[i] + " ");
document.write( "<br>");
}
// Driver Code
let N = 5;
let arr = [ 1, 2, 3, 4, 5 ];
// Function call
findPerm(arr, N);
// This code is contributed by satwik4409.
</script>
Producción
2 1 4 5 3
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N),
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA