Dados tres enteros N , A y B , la tarea es encontrar una permutación de números distintos por pares de 1 a N que tenga exactamente mínimos locales ‘A’ y máximos locales ‘B’ .
- Un mínimo local se define como el elemento que es menor que sus dos vecinos.
- Un máximo local se define como el elemento que es mayor que sus dos vecinos.
- El primer y último elemento de la permutación completa nunca pueden ser mínimos o máximos locales.
Si no existen tales permutaciones, imprima -1 .
Ejemplo :
Entrada: N = 6, A = 2, B = 2
Salida: 1, 3, 2, 5, 4, 6
Explicación:
2 mínimos locales: 2 y 5
2 máximos locales: 3 y 5Entrada: N = 5 , A = 2 , B = 2
Salida: -1
Enfoque ingenuo (fuerza bruta): en este enfoque, genere todas las permutaciones de 1 a N números y verifique cada uno individualmente. Siga los pasos a continuación para resolver este problema:
- Genere todas las permutaciones de números del 1 al N y guárdelas en una array.
- Recorra cada permutación, si la siguiente permutación tiene exactamente A mínimos locales y B máximos locales, imprima la permutación.
- Si no existe tal permutación, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to generate next permutation
void nextPermutation(vector<int>& nums)
{
int n = nums.size(), k, l;
for (k = n - 2; k >= 0; k--) {
if (nums[k] < nums[k + 1]) {
break;
}
}
if (k < 0) {
reverse(nums.begin(), nums.end());
}
else {
for (l = n - 1; l > k; l--) {
if (nums[l] > nums[k]) {
break;
}
}
swap(nums[k], nums[l]);
reverse(nums.begin() + k + 1, nums.end());
}
}
// Factorial function
int factorial(int n)
{
return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}
// Function to returns all the permutations of a given array
// or vector
vector<vector<int> > permute(vector<int>& nums)
{
vector<vector<int> > permuted;
int n = nums.size();
int factn = factorial(n);
for (int i = 0; i < factn; i++) {
permuted.push_back(nums);
nextPermutation(nums);
}
return permuted;
}
// Function to find the permutation of 1 to N numbers
// having A minimas and B maximas
void findPermutation(int n, int a, int b)
{
// Generate the array containing one permutation
vector<int> nums(n);
for (int i = 0; i < n; i++) {
nums[i] = i + 1;
}
// Generate all the permutations
vector<vector<int> > allpermutations = permute(nums);
int total = allpermutations.size();
int ansindex = -1;
for (int i = 0; i < total; i++) {
// Count local minima and local maximas for each
// permutation
int minc = 0, maxc = 0;
for (int j = 1; j < n - 1; j++) {
if (allpermutations[i][j]
> allpermutations[i][j - 1]
&& allpermutations[i][j]
> allpermutations[i][j + 1]) {
maxc++;
}
if (allpermutations[i][j]
< allpermutations[i][j - 1]
&& allpermutations[i][j]
< allpermutations[i][j + 1]) {
minc++;
}
}
if (minc == a && maxc == b) {
// Store the index of a perfect permutation
ansindex = i;
break;
}
}
// Print -1 if no such permutation exists
if (ansindex == -1) {
cout << -1;
}
else {
// Print the perfect permutation if exists
for (int i = 0; i < n; i++) {
cout << allpermutations[ansindex][i] << " ";
}
}
}
int main()
{
int N = 6, A = 2, B = 2;
findPermutation(N, A, B);
return 0;
}
Producción
1 3 2 5 4 6
Complejidad de Tiempo: O(N!)
Espacio Auxiliar: O(N!)
Enfoque eficiente (método codicioso):
El método de fuerza bruta anterior se puede optimizar usando el algoritmo Greedy . Greedy es un paradigma algorítmico que construye una solución pieza por pieza, eligiendo siempre la siguiente pieza que ofrece el beneficio más obvio e inmediato. Entonces, divida el problema en diferentes partes utilizables de acuerdo con los valores de N , A , B . Siga los pasos a continuación para resolver este problema:
- Como el primer y el último elemento de una permutación completa no pueden ser máximos o mínimos, el número total de máximos y mínimos debe ser menor o igual que N-2 . Entonces, si (A + B > N -2) , imprime -1 .
- Además, no puede haber dos mínimos o máximos consecutivos. Debe haber un mínimo entre dos máximos consecutivos y debe haber un máximo entre dos mínimos consecutivos. Entonces, la diferencia absoluta entre el número total de mínimos y máximos debe ser menor o igual a 1. Entonces, si la diferencia absoluta entre A y B excede 1 , imprima -1 . Podemos visualizarlo fácilmente en la imagen de abajo.
- Después de terminar los dos casos de esquina, cree dos variables, minValue para almacenar el valor mínimo de la permutación y maxValue para almacenar el valor máximo. Ahora divide el problema en tres casos diferentes que son (A > B) , (A < B) y (A=B) . Ahora resuelve cada caso individualmente:
- Si (A > B): inicialice minValue como 1 y complete la array con minValue a partir del índice 2 para A veces. Después de cada inserción, aumente minValue en 1, ya que los valores deben ser distintos. Mientras rellena, asegúrese de dejar un índice vacío después de cada inserción, ya que no es posible que dos mínimos residan consecutivamente. Después de crear A mínimos, llene el resto de la array en orden creciente para que no se creen nuevos mínimos.
- Si (B > A): inicialice maxValue como N y llene la array con maxValue a partir del índice 2 por B veces. Después de cada inserción, disminuya maxValue en 1, ya que los valores deben ser distintos. Mientras rellena, asegúrese de dejar un índice vacío después de cada inserción, ya que no es posible que dos máximos residan consecutivamente. Después de crear B máximos, llene el resto de la array en orden decreciente para que no se creen nuevos máximos.
- Si (A = B): luego inicialice dos valores minValue como 1 y maxValue como N . Complete el primer elemento de la array con minValue y aumente minValue en 1. Luego complete los índices pares con maxValue y disminuya maxValue en 1 y complete los índices impares con minValue y aumente minValue en 1 por A veces. Ahora, llena el resto de las posiciones en orden creciente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the permutation of 1 to N numbers
// having A minimas and B maximas
void findPermutation(int N, int A, int B)
{
// Create the result array
vector<int> arr(N);
for (int i = 0; i < N; i++) {
arr[i] = -1;
}
// If the absolute difference between A and B is
// greater 1 or A+B is greater than N-2, then return -1
if (abs(A - B) > 1 || A + B > N - 2) {
cout << -1;
}
else {
if (A > B) {
// Initialize maxValue with N
int maxValue = N;
// Create a maxima's
for (int i = 1; i < N - 1 && A > 0; i += 2) {
arr[i] = maxValue;
maxValue--;
A--;
}
// Fill other elements in decreasing order
for (int i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = maxValue;
maxValue--;
}
}
}
else if (A < B) {
// Initialize minValue with 1
int minValue = 1;
// Create B minima's
for (int i = 1; i < N - 1 && B > 0; i += 2) {
arr[i] = minValue;
minValue++;
B--;
}
// Fill other elements in increasing order
for (int i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = minValue;
minValue++;
}
}
}
else if (A == B) {
// Initialize maxValue with n and minValue with
// 1
int minValue = 1, maxValue = N;
arr[0] = minValue;
minValue++;
// Initialize fill equal number of minima and
// maximas
for (int i = 1; i < N - 1 && A > 0; i += 2) {
arr[i] = maxValue;
arr[i + 1] = minValue;
A--;
maxValue--;
minValue++;
}
// Fill the rest in increasing order
for (int i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = minValue;
minValue++;
}
}
}
// Print the output
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
}
cout << endl;
}
// Driver Code
int main()
{
int N = 6, A = 2, B = 1;
findPermutation(N, A, B);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find the permutation of 1 to N numbers
// having A minimas and B maximas
static void findPermutation(int N, int A, int B)
{
// Create the result array
int []arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = -1;
}
// If the absolute difference between A and B is
// greater 1 or A+B is greater than N-2, then return -1
if (Math.abs(A - B) > 1 || A + B > N - 2) {
System.out.print(-1);
}
else {
if (A > B) {
// Initialize maxValue with N
int maxValue = N;
// Create a maxima's
for (int i = 1; i < N - 1 && A > 0; i += 2) {
arr[i] = maxValue;
maxValue--;
A--;
}
// Fill other elements in decreasing order
for (int i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = maxValue;
maxValue--;
}
}
}
else if (A < B) {
// Initialize minValue with 1
int minValue = 1;
// Create B minima's
for (int i = 1; i < N - 1 && B > 0; i += 2) {
arr[i] = minValue;
minValue++;
B--;
}
// Fill other elements in increasing order
for (int i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = minValue;
minValue++;
}
}
}
else if (A == B) {
// Initialize maxValue with n and minValue with
// 1
int minValue = 1, maxValue = N;
arr[0] = minValue;
minValue++;
// Initialize fill equal number of minima and
// maximas
for (int i = 1; i < N - 1 && A > 0; i += 2) {
arr[i] = maxValue;
arr[i + 1] = minValue;
A--;
maxValue--;
minValue++;
}
// Fill the rest in increasing order
for (int i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = minValue;
minValue++;
}
}
}
// Print the output
for (int i = 0; i < N; i++) {
System.out.print(arr[i]+ " ");
}
}
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
int N = 6, A = 2, B = 1;
findPermutation(N, A, B);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for the above approach # Function to find the permutation of 1 to N numbers # having A minimas and B maximas def findPermutation(N, A, B): # Create the result array arr = [0]*(N) for i in range(N): arr[i] = -1 # If the absolute difference between A and B is # greater 1 or A+B is greater than N-2, then return -1 if (abs(A - B) > 1 or A + B > N - 2): print(-1) else: if (A > B): # Initialize maxValue with N maxValue = N # Create a maxima's i = 1 while i < N - 1 and A > 0: arr[i] = maxValue maxValue -= 1 A -= 1 i += 2 # Fill other elements in decreasing order for i in range(N): if (arr[i] == -1): arr[i] = maxValue maxValue -= 1 elif (A < B): # Initialize minValue with 1 minValue = 1 # Create B minima's i = 1 while i < N - 1 and B > 0: arr[i] = minValue minValue += 1 B -= 1 i += 2 # Fill other elements in increasing order for i in range(N): if (arr[i] == -1): arr[i] = minValue minValue += 1 elif (A == B): # Initialize maxValue with n and minValue with # 1 minValue = 1 maxValue = N arr[0] = minValue minValue += 1 # Initialize fill equal number of minima and # maximas i = 1 while i < N - 1 and A > 0: arr[i] = maxValue arr[i + 1] = minValue A -= 1 maxValue -= 1 minValue += 1 i += 2 # Fill the rest in increasing order for i in range(N): if (arr[i] == -1): arr[i] = minValue minValue += 1 # Print the output for i in range(N): print(arr[i], end=" ") print() # Driver Code if __name__ == "__main__": N = 6 A = 2 B = 1 findPermutation(N, A, B) # This code is contributed by ukasp.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the permutation of 1 to N numbers
// having A minimas and B maximas
static void findPermutation(int N, int A, int B)
{
// Create the result array
int []arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = -1;
}
// If the absolute difference between A and B is
// greater 1 or A+B is greater than N-2, then return -1
if (Math.Abs(A - B) > 1 || A + B > N - 2) {
Console.Write(-1);
}
else {
if (A > B) {
// Initialize maxValue with N
int maxValue = N;
// Create a maxima's
for (int i = 1; i < N - 1 && A > 0; i += 2) {
arr[i] = maxValue;
maxValue--;
A--;
}
// Fill other elements in decreasing order
for (int i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = maxValue;
maxValue--;
}
}
}
else if (A < B) {
// Initialize minValue with 1
int minValue = 1;
// Create B minima's
for (int i = 1; i < N - 1 && B > 0; i += 2) {
arr[i] = minValue;
minValue++;
B--;
}
// Fill other elements in increasing order
for (int i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = minValue;
minValue++;
}
}
}
else if (A == B) {
// Initialize maxValue with n and minValue with
// 1
int minValue = 1, maxValue = N;
arr[0] = minValue;
minValue++;
// Initialize fill equal number of minima and
// maximas
for (int i = 1; i < N - 1 && A > 0; i += 2) {
arr[i] = maxValue;
arr[i + 1] = minValue;
A--;
maxValue--;
minValue++;
}
// Fill the rest in increasing order
for (int i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = minValue;
minValue++;
}
}
}
// Print the output
for (int i = 0; i < N; i++) {
Console.Write(arr[i]+ " ");
}
}
Console.Write("\n");
}
// Driver Code
public static void Main()
{
int N = 6, A = 2, B = 1;
findPermutation(N, A, B);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the permutation of 1 to N numbers
// having A minimas and B maximas
function findPermutation(N, A, B)
{
// Create the result array
let arr = new Array(N);
for (let i = 0; i < N; i++) {
arr[i] = -1;
}
// If the absolute difference between A and B is
// greater 1 or A+B is greater than N-2, then return -1
if (Math.abs(A - B) > 1 || A + B > N - 2) {
document.write(-1);
}
else {
if (A > B) {
// Initialize maxValue with N
let maxValue = N;
// Create a maxima's
for (let i = 1; i < N - 1 && A > 0; i += 2) {
arr[i] = maxValue;
maxValue--;
A--;
}
// Fill other elements in decreasing order
for (let i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = maxValue;
maxValue--;
}
}
}
else if (A < B)
{
// Initialize minValue with 1
let minValue = 1;
// Create B minima's
for (let i = 1; i < N - 1 && B > 0; i += 2) {
arr[i] = minValue;
minValue++;
B--;
}
// Fill other elements in increasing order
for (let i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = minValue;
minValue++;
}
}
}
else if (A == B) {
// Initialize maxValue with n and minValue with
// 1
let minValue = 1, maxValue = N;
arr[0] = minValue;
minValue++;
// Initialize fill equal number of minima and
// maximas
for (let i = 1; i < N - 1 && A > 0; i += 2) {
arr[i] = maxValue;
arr[i + 1] = minValue;
A--;
maxValue--;
minValue++;
}
// Fill the rest in increasing order
for (let i = 0; i < N; i++) {
if (arr[i] == -1) {
arr[i] = minValue;
minValue++;
}
}
}
// Print the output
for (let i = 0; i < N; i++) {
document.write(arr[i] + " ");
}
}
document.write('<br>')
}
// Driver Code
let N = 6, A = 2, B = 1;
findPermutation(N, A, B);
// This code is contributed by Potta Lokesh
</script>
Producción
4 6 3 5 2 1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por akashkumarsen4 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA