Dados tres números enteros N , A y B , la tarea es encontrar una permutación de números distintos por pares de 1 a N tal que A sea el elemento mínimo de la mitad izquierda y B sea el elemento máximo de la mitad derecha. También se da que N es par. Si no existen tales permutaciones, imprima -1 .
Ejemplos:
Entrada: N = 6, A = 2, B = 5
Salida: 6, 2, 4, 3, 5, 1
Explicación: A = 2 es el mínimo de la mitad izquierda.
B = 5 es el máximo de la mitad derecha.Entrada: N = 6, A = 1, B = 3
Salida: -1
Explicación: No existe tal permutación.
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 en la siguiente permutación A es el mínimo de la mitad izquierda y B es el máximo de la mitad derecha, 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++) { // Find the minima of the left half // maxima of the right half int leftmin = allpermutations[i][0]; int rightmax = allpermutations[i][n - 1]; for (int j = 0; j < n / 2; j++) { if (allpermutations[i][j] < leftmin) { leftmin = allpermutations[i][j]; } } for (int j = n / 2; j < n; j++) { if (allpermutations[i][j] > rightmax) { rightmax = allpermutations[i][j]; } } if (leftmin == a && rightmax == 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] << " "; } } } // Driver Code int main() { int N = 6, A = 2, B = 5; findPermutation(N, A, B); return 0; }
Python3
# Python code to implement the above approach num =[] # Function to generate next permutation def nextPermutation(nums): global num n = len(nums) for k in range(n - 2, -1,-1): if (nums[k] < nums[k + 1]): break if (k < 0): nums.reverse() else: for l in range(n - 1, k, -1): if (nums[l] > nums[k]): break nums[k], nums[l] = nums[l], nums[k] temp = nums[k+1:] temp.reverse() nums = nums[:k+1] +temp return nums # Factorial function def factorial(n): return 1 if(n == 1 or n == 0) else factorial(n - 1) * n # Function to returns all the permutations # of a given array or vector def permute(nums): global num permuted =[] n = len(nums) factn = factorial(n) for i in range(factn): permuted.append(nums) nums = nextPermutation(nums) permuted.append(nums) return permuted # Function to find the permutation # of 1 to N numbers # having A minimas and B maximas def findPermutation(n, a, b): # Generate the array # containing one permutation nums = [0]*n for i in range(n): nums[i] = i + 1 # Generate all the permutations allpermutations = permute(nums) total = len(allpermutations) ansindex = -1 for i in range(total): # Find the minima of the left half # maxima of the right half leftmin = allpermutations[i][0] rightmax = allpermutations[i][n - 1] for j in range(n // 2): if (allpermutations[i][j] < leftmin): leftmin = allpermutations[i][j] for j in range(n // 2,n): if (allpermutations[i][j] > rightmax): rightmax = allpermutations[i][j] if (leftmin == a and rightmax == b): # Store the index # of a perfect permutation ansindex = i break # Pr-1 if no such permutation exists if (ansindex == -1): print(-1) else: # Print the perfect permutation if exists for i in range(n): print(allpermutations[ansindex][i], end =" ") # Driver Code N = 6 A = 2 B = 5 findPermutation(N, A, B) # This code is contributed by Shubham Singh
2 3 6 1 4 5
Complejidad de Tiempo: O(N!)
Espacio Auxiliar: O(N!)
Enfoque eficiente (método codicioso): el método de fuerza bruta anterior se puede optimizar utilizando el algoritmo codicioso . 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:
- Inicialice las variables izquierda como nb y derecha como a-1.
- Si izquierda o derecha es mayor que n/2 , imprima -1
- De lo contrario, si a y b son menos que iguales a n/2 , imprima -1.
- De lo contrario, si a y b son mayores que n/2 , imprima -1.
- De lo contrario, si a es igual a n/2+1 y b es igual a n/2 , imprima n en 1 como respuesta.
- De lo contrario, itere sobre el rango [0, n) usando la variable i y realice las siguientes tareas:
- Si ni es igual a a o b , imprima a o b , de lo contrario, imprima ni .
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 get the desired permutation void getpermutation(int n, int a, int b) { int left = n - b, right = a - 1; // When b < n/2 or a > n/2 if (left > n / 2 || right > n / 2) { cout << -1; } // When a and b both are // in the same half else if (a <= n / 2 && b <= n / 2) { cout << -1; } else if (a > n / 2 && b > n / 2) { cout << -1; } // The corner case else if (a == n / 2 + 1 && b == n / 2) { for (int i = 0; i < n; i++) { cout << n - i << " "; } } // Rest other combinations else { for (int i = 0; i < n; i++) { if (n - i == b) { cout << a << " "; } else if (n - i == a) { cout << b << " "; } else { cout << n - i << " "; } } } cout << endl; } // Driver Code int main() { int N = 6, A = 2, B = 5; getpermutation(N, A, B); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to get the desired permutation static void getpermutation(int n, int a, int b) { int left = n - b, right = a - 1; // When b < n/2 or a > n/2 if (left > n / 2 || right > n / 2) { System.out.print(-1); } // When a and b both are // in the same half else if (a <= n / 2 && b <= n / 2) { System.out.print(-1); } else if (a > n / 2 && b > n / 2) { System.out.print(-1); } // The corner case else if (a == n / 2 + 1 && b == n / 2) { for(int i = 0; i < n; i++) { System.out.print(n - i + " "); } } // Rest other combinations else { for(int i = 0; i < n; i++) { if (n - i == b) { System.out.print(a + " "); } else if (n - i == a) { System.out.print(b + " "); } else { System.out.print(n - i + " "); } } } System.out.println(); } // Driver Code public static void main(String args[]) { int N = 6, A = 2, B = 5; getpermutation(N, A, B); } } // This code is contributed by Samim Hossain Mondal.
Python3
# python program for the above approach # Function to get the desired permutation def getpermutation(n, a, b): left = n - b right = a - 1 # When b < n/2 or a > n/2 if (left > n / 2 or right > n / 2): print(-1) # When a and b both are # in the same half elif (a <= n / 2 and b <= n / 2): print(-1) elif (a > n / 2 and b > n / 2): print(-1) # The corner case elif (a == n / 2 + 1 and b == n / 2): for i in range(0, n): print(n - i, end=" ") # Rest other combinations else: for i in range(0, n): if (n - i == b): print(a, end=" ") elif (n - i == a): print(b, end=" ") else: print(n - i, end=" ") print() # Driver Code if __name__ == "__main__": N = 6 A = 2 B = 5 getpermutation(N, A, B) # This code is contributed by rakeshsahni
C#
// C# program for the above approach using System; class GFG { // Function to get the desired permutation static void getpermutation(int n, int a, int b) { int left = n - b, right = a - 1; // When b < n/2 or a > n/2 if (left > n / 2 || right > n / 2) { Console.Write(-1); } // When a and b both are // in the same half else if (a <= n / 2 && b <= n / 2) { Console.Write(-1); } else if (a > n / 2 && b > n / 2) { Console.Write(-1); } // The corner case else if (a == n / 2 + 1 && b == n / 2) { for (int i = 0; i < n; i++) { Console.Write(n - i + " "); } } // Rest other combinations else { for (int i = 0; i < n; i++) { if (n - i == b) { Console.Write(a + " "); } else if (n - i == a) { Console.Write(b + " "); } else { Console.Write(n - i + " "); } } } Console.WriteLine(); } // Driver Code public static void Main() { int N = 6, A = 2, B = 5; getpermutation(N, A, B); } } // This code is contributed by ukasp.
Javascript
<script> // JavaScript code for the above approach // Function to get the desired permutation function getpermutation(n, a, b) { let left = n - b, right = a - 1; // When b < n/2 or a > n/2 if (left > Math.floor(n / 2) || right > Math.floor(n / 2)) { document.write(-1 + " "); } // When a and b both are // in the same half else if (a <= Math.floor(n / 2) && b <= Math.floor(n / 2)) { document.write(-1 + " "); } else if (a > Math.floor(n / 2) && b > Math.floor(n / 2)) { document.write(-1 + " "); } // The corner case else if (a == Math.floor(n / 2) + 1 && b == Math.floor(n / 2)) { for (let i = 0; i < n; i++) { document.write(n - i + " "); } } // Rest other combinations else { for (let i = 0; i < n; i++) { if (n - i == b) { document.write(a + " ") } else if (n - i == a) { document.write(b + " ") } else { document.write(n - i + " ") } } } cout << endl; } // Driver Code let N = 6, A = 2, B = 5; getpermutation(N, A, B); // This code is contributed by Potta Lokesh </script>
6 2 4 3 5 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