Permutación lexicográficamente más pequeña de tamaño A que tiene B enteros que exceden todos los enteros anteriores

Dados dos enteros positivos, A y B , la tarea es generar la permutación lexicográficamente más pequeña de todos los enteros hasta A en la que exactamente los enteros B son mayores que todos sus elementos anteriores.

Ejemplos:

Entrada: A = 3, B = 2
Salida: [1, 3, 2]
Explicación:
Todas las posibles permutaciones de enteros [1, 3] son ​​[(1, 2, 3), (1, 3, 2), (2 , 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]. De estas permutaciones, tres permutaciones {(1, 3, 2), (2, 1, 3), (2, 3, 1)} satisfacen la condición necesaria. La permutación lexicográficamente más pequeña de las tres es (1, 3, 2).

Entrada: A = 4, B = 4
Salida: [1, 2, 3, 4]

Enfoque: siga los pasos a continuación para resolver el problema:

  1. Genere todas las permutaciones posibles de enteros de [1, A] usando la función incorporada permutations() de la biblioteca itertools . Básicamente, devuelve una tupla que consta de todas las permutaciones posibles.
  2. Ahora, verifique si el elemento máximo de la array y la cantidad de elementos que deben satisfacer la condición del problema son iguales o no.
  3. Si es igual, solo hay una lista posible de elementos que satisfacen la condición. Lógicamente son simplemente el rango de Un número de enteros comenzando desde 1 en orden ordenado.
  4. Si no, tome cada tupla de la lista de permutaciones y luego calcule el número de enteros que están presentes en la tupla que es mayor que todos los enteros anteriores en esa tupla.
  5. Si el recuento es igual a B , cargue esa tupla en otra lista nueva.
  6. Pruebe las listas de elementos que se cargan con una nueva lista, ya sea que estén ordenados lexicográficamente o no, si no están ordenados, luego organícelos manualmente y devuelva el mínimo.

A continuación se muestra la implementación del enfoque anterior:

Python3

# Python3 program for the above approach
from itertools import permutations
 
# Function to find lexicographically
# smallest permutation of [1, A]
# having B integers greater than
# all the previous elements
 
def getSmallestArray(A, B):
 
    # if A and B are equal
    if A == B:
        return list(range(1, A + 1))
 
    # Initialize pos_list to store list
    # of elements which are satisfying
    # the given conditions
    pos_list = []
 
    # List to store all possible permutations
    Main_List = list(permutations(range(1, A + 1), A))
 
    # Check all the permutations for
    # the given condition
    for L in Main_List:
 
        # Stores the count of elements
        # greater than all the previous
        # elements
        c = 0
 
        i = 0
        j = 1
        while j <= (len(L)-1):
 
            if L[j] > L[i]:
                i += 1
 
            elif i == j:
                c += 1
                j += 1
                i = 0
 
            else:
                j += 1
                i = 0
 
        # If count is equal to B
        if (c + 1) == B:
 
            pos_list.append(list(L))
 
    # If only one tuple satisfies
    # the given condition
    if len(pos_list) == 1:
 
        return pos_list[0]
 
    # Otherwise
    satisfied_list = []
    for i in pos_list:
 
        array_test = ''.join(map(str, i))
        satisfied_list.append(int(array_test))
 
        # Evaluate lexicographically smallest tuple
    small = min(satisfied_list)
    str_arr = list(str(small))
    ans = list(map(int, str_arr))
 
    # Return the answer
    return ans
 
 
# Driver Code
 
A = 3
B = 2
 
print(getSmallestArray(A, B))
Producción: 

[1, 3, 2]

 

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )

Enfoque eficiente: siga los pasos a continuación para optimizar el enfoque anterior:

  1. Inicialice una array arr[] que consta de los primeros números naturales A secuencialmente.
  2. Cree una array resultante ans[] y agregue los primeros elementos (B – 1) de arr[] .
  3. Entonces, la array resultante tiene (B – 1) elementos que satisfacen la condición dada.
  4. Ahora inserte el elemento máximo de arr[] en la array resultante. Eliminar los elementos insertados arr[]
  5. Como ya tenemos B elementos, la array resultante tiene B elementos que satisfacen la condición dada.
  6. Ahora, copie todos los elementos restantes de arr[] uno por uno a la array resultante e imprima la array resultante.

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 lexicographically
// smallest permutation of [1, A]
// having B integers greater than
// all the previous elements
vector<int> getSmallestArray(int A, int B)
{
     
    // Initial array
    vector<int>arr(A);
    for(int i = 0; i < A; i++)
        arr[i] = i + 1;
         
    // Resultant array
    vector<int>ans(A);
 
    // Append the first (B-1) elements
    // to the resultant array 
    for(int i = 0; i < B - 1; i++)
        ans[i] = arr[i];
         
    // Append the maximum from the
    // initial array 
    ans[B - 1] = arr[A - 1];
     
    // Copy the remaining elements 
    for(int i = B; i < A; i++)
        ans[i] = arr[i - 1];
         
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    int A = 3;
    int B = 2;
     
    vector<int>ans = getSmallestArray(A, B);
     
    for(auto i : ans)
        cout << i << " ";
}
 
// This code is contributed by Stream_Cipher

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find lexicographically
// smallest permutation of [1, A]
// having B integers greater than
// all the previous elements
@SuppressWarnings("unchecked")
static void getSmallestArray(int A, int B)
{
     
    // Initial array
    Vector arr = new Vector();
    for(int i = 0; i < A; i++)
        arr.add(i + 1);
         
    // Resultant array
    Vector ans = new Vector();
 
    // Append the first (B-1) elements
    // to the resultant array 
    for(int i = 0; i < B - 1; i++)
        ans.add(arr.get(i));
         
    // Append the maximum from the
    // initial array 
    ans.add(arr.get(A - 1));
     
    // Copy the remaining elements 
    for(int i = B; i < A; i++)
        ans.add(arr.get(i - 1));
         
    // Print the answer
    for(int i = 0; i < ans.size(); i++)
        System.out.print(ans.get(i) + " ");
}
 
// Driver Code
public static void main(String args[])
{
    int A = 3;
    int B = 2;
     
    getSmallestArray(A, B);
}
}
 
// This code is contributed by Stream_Cipher

Python3

# Python3 program for the above approach
 
# Function to find lexicographically
# smallest permutation of [1, A]
# having B integers greater than
# all the previous elements
 
def getSmallestArray(A, B):
 
    # Initial array
    arr = (list(range(1, (A + 1))))
 
    # Resultant array
    ans = []
 
    # Append the first (B-1) elements
    # to the resultant array
    ans[0:B-1] = arr[0:B-1]
 
    # Delete the appended elements
    # from the initial array
    del arr[0:B-1]
 
    # Append the maximum from the
    # initial array
    ans.append(arr[-1])
 
    # Delete the appended maximum
    del arr[-1]
 
    # Copy the remaining elements
    ans[B:] = arr[:]
 
    # Return the answer
    return ans
 
# Driver Code
 
A = 3
B = 2
 
print(getSmallestArray(A, B))

C#

// C# program for the above approach
using System.Collections.Generic;
using System;
 
class GFG{
 
// Function to find lexicographically
// smallest permutation of [1, A]
// having B integers greater than
// all the previous elements
 static void getSmallestArray(int A, int B)
{
     
    // Initial array
    List<int> arr = new List<int>();
    for(int i = 0; i < A; i++)
        arr.Add(i + 1);
         
    // Resultant array
    List<int> ans = new List<int>();
 
    // Append the first (B-1) elements
    // to the resultant array 
    for(int i = 0; i < B - 1; i++)
        ans.Add(arr[i]);
         
    // Append the maximum from the
    // initial array 
    ans.Add(arr[A - 1]);
     
    // Copy the remaining elements 
    for(int i = B; i < A; i++)
        ans.Add(arr[i - 1]);
         
    // Print the answer
    for(int i = 0; i < A; i++)
        Console.Write(ans[i] + " ");
}
 
// Driver Code
public static void Main()
{
    int A = 3;
    int B = 2;
     
    getSmallestArray(A,B);
}
}
 
// This code is contributed by Stream_Cipher

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find lexicographically
// smallest permutation of [1, A]
// having B integers greater than
// all the previous elements
function getSmallestArray( A, B)
{
     
    // Initial array
    let arr = [];
 
    for(let i = 0; i < A; i++)
        arr[i] = i + 1;
         
    // Resultant array
    let ans = [];
    for(let i = 0;i<A;i++)
        ans.push(0);
 
    // Append the first (B-1) elements
    // to the resultant array 
    for(let i = 0; i < B - 1; i++)
        ans[i] = arr[i];
 
    // Append the maximum from the
    // initial array 
    ans[B - 1] = arr[A - 1];
 
    // Copy the remaining elements 
    for(let i = B; i < A; i++)
        ans[i] = arr[i - 1];
    // Return the answer
    return ans;
}
 
// Driver Code
let A = 3;
let B = 2;
let ans = getSmallestArray(A, B);
for(let i =0;i<ans.length;i++)
       document.write( ans[i] ," ");
 
</script>
Producción: 

[1, 3, 2]

 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por rakesh419 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *