Dada una string binaria S de tamaño (N – 1) , la tarea es encontrar la permutación lexicográficamente más pequeña P de los primeros N números naturales tal que para cada índice i , si S[i] es igual a ‘ 0 ‘ entonces P[i + 1] debe ser mayor que P[i] y si S[i] es igual a ‘ 1 ‘ entonces P[i + 1] debe ser menor que P[i] .
Ejemplos:
Entrada: N = 7, S = 1 00101
Salida: 2 1 3 5 4 7 6
Explicación:
Considere la permutación como {2, 1, 3, 5, 4, 7, 6} que satisface los criterios dados como:
Para el índice 0 , S[0] = 1, P[1] < P[0], es decir, 1 < 2
para índice 1, S[1] = 0, P[2] < P[1], es decir, 3 > 1
para índice 2 , S[2] = 0, P[3] < P[2], es decir, 5 > 3
para índice 3, S[3] = 1, P[4] < P[3], es decir, 4 < 5
para índice 4 , S[4] = 0, P[5] < P[4], es decir, 7 > 4
Para el índice 5, S[5] = 1, P[6] < P[5], es decir, 6 < 7Entrada: N = 4, S = 000
Salida: 1 2 3 4
Enfoque: El problema dado se puede resolver utilizando el enfoque codicioso utilizando números más pequeños en índices más bajos tanto como sea posible creará las permutaciones lexicográficamente más pequeñas. Siga los pasos a continuación para resolver el problema:
- Inicialice una array , digamos ans[] de tamaño N que almacene la permutación resultante .
- Atraviese la string S dada y realice los siguientes pasos:
- Si el valor de S[i] es igual a ‘ 0 ‘, asigne el número mayor que el último número asignado.
- De lo contrario, asigne el número más pequeño que sea mayor que todos los números utilizados actualmente.
- Después de completar los pasos anteriores, imprima la permutación resultante formada en la array ans[] .
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 the lexicographically
// smallest permutation according to the
// given criteria
void constructPermutation(string S, int N)
{
// Stores the resultant permutation
int ans[N];
// Initialize the first elements to 1
ans[0] = 1;
// Traverse the given string S
for (int i = 1; i < N; ++i) {
if (S[i - 1] == '0') {
// Number greater than last
// number
ans[i] = i + 1;
}
else {
// Number equal to the last
// number
ans[i] = ans[i - 1];
}
// Correct all numbers to the left
// of the current index
for (int j = 0; j < i; ++j) {
if (ans[j] >= ans[i]) {
ans[j]++;
}
}
}
// Printing the permutation
for (int i = 0; i < N; i++) {
cout << ans[i];
if (i != N - 1) {
cout << " ";
}
}
}
// Driver Code
int main()
{
string S = "100101";
constructPermutation(S, S.length() + 1);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to generate the lexicographically
// smallest permutation according to the
// given criteria
static void constructPermutation(String S, int N)
{
// Stores the resultant permutation
int[] ans = new int[N];
// Initialize the first elements to 1
ans[0] = 1;
// Traverse the given string S
for (int i = 1; i < N; ++i) {
if (S.charAt(i - 1) == '0') {
// Number greater than last
// number
ans[i] = i + 1;
}
else {
// Number equal to the last
// number
ans[i] = ans[i - 1];
}
// Correct all numbers to the left
// of the current index
for (int j = 0; j < i; ++j) {
if (ans[j] >= ans[i]) {
ans[j]++;
}
}
}
// Printing the permutation
for (int i = 0; i < N; i++) {
System.out.print(ans[i]);
if (i != N - 1) {
System.out.print(" ");
}
}
}
// Driver Code
public static void main(String[] args) {
String S = "100101";
constructPermutation(S, S.length() + 1);
}
}
// This code is contributed by code_hunt.
Python3
# Python Program to implement
# the above approach
# Function to generate the lexicographically
# smallest permutation according to the
# given criteria
def constructPermutation(S, N):
# Stores the resultant permutation
ans = [0] * N
# Initialize the first elements to 1
ans[0] = 1
# Traverse the given string S
for i in range(1, N):
if (S[i - 1] == '0'):
# Number greater than last
# number
ans[i] = i + 1
else :
# Number equal to the last
# number
ans[i] = ans[i - 1]
# Correct all numbers to the left
# of the current index
for j in range(i):
if (ans[j] >= ans[i]):
ans[j] += 1
# Printing the permutation
for i in range(N):
print(ans[i], end="")
if (i != N - 1):
print(" ", end="")
# Driver Code
S = "100101"
constructPermutation(S, len(S) + 1)
# This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
class GFG {
// Function to generate the lexicographically
// smallest permutation according to the
// given criteria
static void constructPermutation(string S, int N)
{
// Stores the resultant permutation
int[] ans = new int[N];
// Initialize the first elements to 1
ans[0] = 1;
// Traverse the given string S
for (int i = 1; i < N; ++i) {
if (S[i - 1] == '0') {
// Number greater than last
// number
ans[i] = i + 1;
}
else {
// Number equal to the last
// number
ans[i] = ans[i - 1];
}
// Correct all numbers to the left
// of the current index
for (int j = 0; j < i; ++j) {
if (ans[j] >= ans[i]) {
ans[j]++;
}
}
}
// Printing the permutation
for (int i = 0; i < N; i++) {
Console.Write(ans[i]);
if (i != N - 1) {
Console.Write(" ");
}
}
}
// Driver Code
public static void Main()
{
string S = "100101";
constructPermutation(S, S.Length + 1);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to generate the lexicographically
// smallest permutation according to the
// given criteria
function constructPermutation(S, N) {
// Stores the resultant permutation
let ans = new Array(N);
// Initialize the first elements to 1
ans[0] = 1;
// Traverse the given string S
for (let i = 1; i < N; ++i) {
if (S[i - 1] == '0') {
// Number greater than last
// number
ans[i] = i + 1;
}
else {
// Number equal to the last
// number
ans[i] = ans[i - 1];
}
// Correct all numbers to the left
// of the current index
for (let j = 0; j < i; ++j) {
if (ans[j] >= ans[i]) {
ans[j]++;
}
}
}
// Printing the permutation
for (let i = 0; i < N; i++) {
document.write(ans[i]);
if (i != N - 1) {
document.write(" ");
}
}
}
// Driver Code
let S = "100101";
constructPermutation(S, S.length + 1);
// This code is contributed by Potta Lokesh
</script>
2 1 3 5 4 7 6
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA