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:
- 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.
- 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.
- 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.
- 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.
- Si el recuento es igual a B , cargue esa tupla en otra lista nueva.
- 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:
- Inicialice una array arr[] que consta de los primeros números naturales A secuencialmente.
- Cree una array resultante ans[] y agregue los primeros elementos (B – 1) de arr[] .
- Entonces, la array resultante tiene (B – 1) elementos que satisfacen la condición dada.
- Ahora inserte el elemento máximo de arr[] en la array resultante. Eliminar los elementos insertados arr[]
- Como ya tenemos B elementos, la array resultante tiene B elementos que satisfacen la condición dada.
- 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)