Encuentre una permutación de 1 a N, tal que A sea mínimo en la mitad izquierda y B sea máximo en la mitad derecha

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++ 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;
}

# 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++ 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 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.

# 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# 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.

<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)