Permutación lexicográficamente más grande mediante la inserción secuencial de elementos de array en los extremos

Dada una array arr[] de N enteros, la tarea es encontrar la permutación lexicográficamente más grande insertando secuencialmente los elementos de la array al frente o al reverso de otra array.

Ejemplos:

Entrada: arr[] = {3, 1, 2, 4}
Salida: 4 3 1 2
Explicación:
las permutaciones que se pueden crear insertando secuencialmente los elementos de la array en la parte delantera o trasera del contenedor son {3, 1, 2, 4}, {1, 3, 2, 4}, {2, 3, 1, 4}, {2, 1, 3, 4}, {4, 1, 3, 2}, {4, 2, 3, 1}, {4, 2, 1, 3} y {4, 3, 1, 2}. De los cuales {4, 3, 1, 2} es la permutación lexicográficamente más grande.

Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 5 4 3 2 1

 

Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso usando el deque que se basa en la observación de que si el elemento de array actual es al menos el primer elemento de la nueva array, la opción más óptima siempre es insertar ese elemento en frente al contenedor para maximizar lexicográficamente la permutación. De lo contrario, inserte el elemento al final de la array. Siga los pasos a continuación para resolver el problema dado:

  • Inicialice un deque , digamos DQ , que almacena el estado actual del contenedor.
  • Inicialice una variable, digamos mx , que almacene el máximo hasta que cada índice represente el 1er elemento del deque DQ .
  • Recorra la array dada arr[] y si el elemento actual arr[i] >= mx , luego inserte arr[i] al frente del deque DQ y actualice el valor de mx . De lo contrario, inserte arr[i] en la parte posterior del deque DQ .
  • Después de completar los pasos anteriores, imprima los elementos almacenados en el deque DQ como la permutación más grande 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 the lexicographically
// largest permutation by sequentially
// inserting the array elements
void largestPermutation(int arr[], int N)
{
 
    // Stores the current state of
    // the new array
    deque<int> p;
 
    // Stores the current maximum
    // element of array arr[]
    int mx = arr[0];
    p.push_back(arr[0]);
 
    // Iterate the array elements
    for (int i = 1; i < N; i++) {
 
        // If the current element is
        // smaller than the current
        // maximum, then insert
        if (arr[i] < mx)
            p.push_back(arr[i]);
 
        // If the current element is
        // at least the current maximum
        else {
            p.push_front(arr[i]);
 
            // Update the value of
            // the current maximum
            mx = arr[i];
        }
    }
 
    // Print resultant permutation
    for (auto i : p)
        cout << i << " ";
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 1, 2, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    largestPermutation(arr, N);
 
    return 0;
}

Java

// Java code for the above approach
import java.util.*;
 
class GFG {
 
    // Function to find the lexicographically
    // largest permutation by sequentially
    // inserting the array elements
    static void largestPermutation(int arr[], int N)
    {
 
        // Stores the current state of
        // the new array
        Deque<Integer> p = new LinkedList<Integer>();
 
        // Stores the current maximum
        // element of array arr[]
        int mx = arr[0];
        p.addLast(arr[0]);
 
        // Iterate the array elements
        for (int i = 1; i < N; i++) {
 
            // If the current element is
            // smaller than the current
            // maximum, then insert
            if (arr[i] < mx)
                p.addLast(arr[i]);
 
            // If the current element is
            // at least the current maximum
            else {
                p.addFirst(arr[i]);
 
                // Update the value of
                // the current maximum
                mx = arr[i];
            }
        }
 
        // Print resultant permutation
        for (Iterator itr = p.iterator(); itr.hasNext();) {
            System.out.print(itr.next() + " ");
        }
    }
 
    // Driver Code
 
    public static void main(String[] args)
    {
        int arr[] = { 3, 1, 2, 4 };
        int N = arr.length;
 
        largestPermutation(arr, N);
    }
}
 
// This code is contributed by Potta Lokesh

Python3

# python program for the above approach
 
# Function to find the lexicographically
# largest permutation by sequentially
# inserting the array elements
from typing import Deque
 
def largestPermutation(arr, N):
 
    # Stores the current state of
    # the new array
    p = Deque()
 
    # Stores the current maximum
    # element of array arr[]
    mx = arr[0]
    p.append(arr[0])
 
    # Iterate the array elements
    for i in range(1, N):
 
        # If the current element is
        # smaller than the current
        # maximum, then insert
        if (arr[i] < mx):
            p.append(arr[i])
 
        # If the current element is
        # at least the current maximum
        else:
            p.appendleft(arr[i])
 
            # Update the value of
            # the current maximum
            mx = arr[i]
 
    # Print resultant permutation
    for i in p:
        print(i, end=" ")
 
# Driver Code
if __name__ == "__main__":
 
    arr = [3, 1, 2, 4]
    N = len(arr)
 
    largestPermutation(arr, N)
 
# This code is contributed by rakeshsahni

C#

// C# code for the above approach
using System;
using System.Linq;
using System.Collections.Generic;
public class GFG {
 
  // Function to find the lexicographically
  // largest permutation by sequentially
  // inserting the array elements
  static void largestPermutation(int []arr, int N) {
 
    // Stores the current state of
    // the new array
    List<int> p = new List<int>();
 
    // Stores the current maximum
    // element of array []arr
    int mx = arr[0];
    p.Add(arr[0]);
 
    // Iterate the array elements
    for (int i = 1; i < N; i++) {
 
      // If the current element is
      // smaller than the current
      // maximum, then insert
      if (arr[i] < mx)
        p.Add(arr[i]);
 
      // If the current element is
      // at least the current maximum
      else {
        p.Insert(0,arr[i]);
 
        // Update the value of
        // the current maximum
        mx = arr[i];
      }
    }
 
    // Print resultant permutation
    foreach (int itr in p) {
      Console.Write(itr + " ");
    }
  }
 
  // Driver Code
  public static void Main(String[] args) {
    int []arr = { 3, 1, 2, 4 };
    int N = arr.Length;
 
    largestPermutation(arr, N);
  }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the lexicographically
// largest permutation by sequentially
// inserting the array elements
function largestPermutation(arr, N)
{
 
  // Stores the current state of
  // the new array
  let p = [];
 
  // Stores the current maximum
  // element of array arr[]
  let mx = arr[0];
  p.push(arr[0]);
 
  // Iterate the array elements
  for (let i = 1; i < N; i++)
  {
   
    // If the current element is
    // smaller than the current
    // maximum, then insert
    if (arr[i] < mx) p.push(arr[i]);
     
    // If the current element is
    // at least the current maximum
    else {
      p.unshift(arr[i]);
 
      // Update the value of
      // the current maximum
      mx = arr[i];
    }
  }
 
  // Print resultant permutation
  for (i of p) document.write(i + " ");
}
 
// Driver Code
 
let arr = [3, 1, 2, 4];
let N = arr.length;
 
largestPermutation(arr, N);
 
// This code is contributed by gfgking.
</script>
Producción: 

4 3 1 2

 

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

Publicación traducida automáticamente

Artículo escrito por shreyanshgupta838 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 *