Dado un entero positivo N , la tarea es encontrar la permutación de los primeros N números naturales , digamos arr[] tal que (arr[i] != i + 1) y la suma de la diferencia absoluta entre arr[i] y (i + 1) es mínimo .
Ejemplos:
Entrada: N = 4
Salida: 2 1 4 3
Explicación:
Considere la permutación {2, 1, 4, 3}, ahora, la suma es abs (2 – 1) + abs (1 – 2) + abs (4 – 3) ) + abs(3 – 4) = 1 + 1 + 1 + 1 = 4, que es el mínimo.Entrada: N = 7
Salida: 2 1 4 3 6 7 5
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las permutaciones posibles de los primeros N números naturales e imprimir esa permutación que satisface los criterios dados.
Complejidad temporal: O(N!)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar observando el hecho de que la array resultante se puede formar intercambiando pares adyacentes alternos para permitir la nueva posición con la suma mínima de la diferencia absoluta entre arr[i] y (i + 1) . En caso de que N sea mayor que 1 y N sea impar, el último elemento puede intercambiarse por cualquiera de los penúltimos o antepenúltimos elementos de la permutación. Siga los pasos a continuación para resolver el problema dado:
- Inicialice una array, digamos arr[] con el primer N número natural dispuesto en orden ascendente.
- Atraviese la array e intercambie todos los elementos adyacentes como swap ( arr[i], arr[i – 1]) .
- Ahora, si el valor de N es mayor que 1 y N es impar, entonces swap(arr[N – 1], arr[N – 2]) .
- Después de completar los pasos anteriores, imprima la array arr[] como la permutación resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
// Function to generate the permutation
// of the first N natural numbers having
// sum of absolute difference between
// element and indices as minimum
#include <iostream>
using namespace std;
void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}
void findPermutation(int N)
{
// Initialize array arr[] from 1 to N
int arr[N];
for (int i = 0; i < N; i++) {
arr[i] = i + 1;
}
for (int i = 1; i < N; i += 2) {
// Swap alternate positions
swap(arr[i], arr[i - 1]);
}
// Check N is greater than 1 and
// N is odd
if (N % 2 == 1 && N > 1) {
// Swapping last two positions
swap(arr[N - 1], arr[N - 2]);
}
// Print the permutation
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
}
// Driver code
int main()
{
int N = 7;
findPermutation(N);
return 0;
}
// This code is contributed by Parth Manchanda
Java
// Java program for the above approach
// Function to generate the permutation
// of the first N natural numbers having
// sum of absolute difference between
// element and indices as minimum
import java.util.*;
class GFG{
static void findPermutation(int N)
{
// Initialize array arr[] from 1 to N
int[] arr = new int[N];
int temp;
for(int i = 0; i < N; i++)
{
arr[i] = i + 1;
}
for(int i = 1; i < N; i += 2)
{
// Swap alternate positions
temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
}
// Check N is greater than 1 and
// N is odd
if (N % 2 == 1 && N > 1)
{
// Swapping last two positions
temp = arr[N - 1];
arr[N - 1] = arr[N - 2];
arr[N - 2] = temp;
}
// Print the permutation
for(int i = 0; i < N; i++)
{
System.out.print(arr[i] + " ");
}
}
// Driver code
public static void main(String[] args)
{
int N = 7;
findPermutation(N);
}
}
// This code is contributed by subhammahato348
Python3
# Python3 program for the above approach # Function to generate the permutation # of the first N natural numbers having # sum of absolute difference between # element and indices as minimum def findPermutation(N): # Initialize array arr[] from 1 to N arr = [i + 1 for i in range(N)] # Swap alternate positions for i in range(1, N, 2): arr[i], arr[i-1] = arr[i-1], arr[i] # Check N is greater than 1 and # N is odd if N % 2 and N > 1: # Swapping last two positions arr[-1], arr[-2] = arr[-2], arr[-1] # Print the permutation for i in arr: print(i, end = " ") # Driver Code if __name__ == '__main__': N = 7 findPermutation(N)
C#
// C# program for the above approach
// Function to generate the permutation
// of the first N natural numbers having
// sum of absolute difference between
// element and indices as minimum
using System;
class GFG {
static void findPermutation(int N)
{
// Initialize array arr[] from 1 to N
int[] arr = new int[N];
int temp;
for (int i = 0; i < N; i++) {
arr[i] = i + 1;
}
for (int i = 1; i < N; i += 2) {
// Swap alternate positions
temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
}
// Check N is greater than 1 and
// N is odd
if (N % 2 == 1 && N > 1) {
// Swapping last two positions
temp = arr[N - 1];
arr[N - 1] = arr[N - 2];
arr[N - 2] = temp;
}
// Print the permutation
for (int i = 0; i < N; i++) {
Console.Write(arr[i] + " ");
}
}
// Driver code
public static void Main()
{
int N = 7;
findPermutation(N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to generate the permutation
// of the first N natural numbers having
// sum of absolute difference between
// element and indices as minimum
function findPermutation(N)
{
var i;
// Initialize array arr[] from 1 to N
var arr = new Array(N);
for(i = 0; i < N; i++)
{
arr[i] = i + 1;
}
for(i = 1; i < N; i += 2)
{
// Swap alternate positions
var temp = arr[i];
arr[i] = arr[i - 1];
arr[i - 1] = temp;
}
// Check N is greater than 1 and
// N is odd
if (N % 2 == 1 && N > 1)
{
// Swapping last two positions
var temp = arr[N - 1];
arr[N - 1] = arr[N - 2];
arr[N - 2] = temp;
}
// Print the permutation
for(i = 0; i < N; i++)
{
document.write(arr[i] + " ");
}
}
// Driver code
var N = 7;
findPermutation(N);
// This code is contributed by SURENDRA_GANGWAR
</script>
2 1 4 3 6 7 5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)