Array lexicográficamente más pequeña formada por como máximo un intercambio para cada par de índices adyacentes

Dada una array A[] de longitud N , la tarea es encontrar la array lexicográficamente más pequeña intercambiando elementos adyacentes para cada índice al menos una vez. Así, para cualquier índice: 

, se permite como máximo un intercambio entre A[K] y A[K+1].
Ejemplo: 
 

Entrada: A[] = { 3, 2, 1, 4} 
Salida: 1 3 2 4 
Explicación: Realice los siguientes intercambios: 
Intercambie A[1] y A[2], ahora A[] = { 3, 1, 2 , 4 } 
Intercambiar A[0] y A[1], ahora A[] = { 1, 3, 2, 4 } 
No se pueden realizar más intercambios ya que A[1] y A[2] ya se intercambiaron.
Entrada: A[] = { 2, 1, 4, 3, 6, 5 } 
Salida: 1 2 3 4 5 6 
Explicación: Realice los siguientes intercambios: 
Intercambie A[0] y A[1], ahora A[] = { 1, 2, 4, 3, 6, 5 } 
Intercambiar A[2] y A[3], ahora A[] = { 1, 2, 3, 4, 6, 5 } 
Intercambiar A[4] y A[ 5], ahora A[] = { 1, 2, 3, 4, 5, 6 } 
 

Enfoque: 
Para resolver el problema mencionado anteriormente, podemos aplicar el método Greedy . Sabemos que podemos realizar como máximo N – 1 intercambios para hacer que la array dada sea lo más pequeña posible. 
 

• Cree una variable de contador e inicialice con N-1 y un mapa hash para almacenar los intercambios realizados.
• Encuentre la posición del elemento mínimo desde el índice actual en adelante.
• Ahora realice el intercambio hacia atrás hasta que lleguemos a la posición actual del elemento.
• También verifique si el intercambio actual es posible o no y disminuya el contador también en cada intercambio.
• Finalmente imprima la array requerida.

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

// C++ implementation to find the
// lexicographically smallest
// array by at most single swap
// for every pair of adjacent indices
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the
// lexicographically smallest array
void findSmallestArray(int A[], int n)
{
    // maximum swaps possible
    int count = n - 1;
  
    // hash to store swaps performed
    map<pair<int, int>, int> mp;
  
    for (int i = 0; i < n && count > 0; ++i) {
  
        // let current element be
        // the minimum possible
        int mn = A[i], pos = i;
  
        // Find actual position of
        // the minimum element
        for (int j = i + 1; j < n; ++j) {
  
            // Update minimum element and
            // its position
            if (A[j] < mn) {
                mn = A[j];
                pos = j;
            }
        }
  
        // Perform swaps if possible
        while (pos > i && count > 0
               && !mp[{ pos - 1, pos }]) {
  
            // Insert current swap in hash
            mp[{ pos - 1, pos }] = 1;
  
            swap(A[pos], A[pos - 1]);
            --pos;
            --count;
        }
    }
  
    // print the required array
    for (int i = 0; i < n; ++i)
        cout << A[i] << " ";
}
  
// Driver code
int main()
{
  
    int A[] = { 2, 1, 4, 3, 6, 5 };
    int n = sizeof(A) / sizeof(A[0]);
  
    findSmallestArray(A, n);
  
    return 0;
}

# Python3 implementation to find the
# lexicographically smallest array by
# at most single swap for every pair
# of adjacent indices
  
# Function to find the
# lexicographically smallest array
def findSmallestArray(A, n):
      
    # Maximum swaps possible
    count = n - 1
  
    # Hash to store swaps performed
    mp = {''}
  
    for i in range(0, n):
        if(count <= 0):
            break;
  
        # Let current element be
        # the minimum possible
        mn = A[i]
        pos = i
  
        # Find actual position of
        # the minimum element
        for j in range(i + 1, n):
  
            # Update minimum element 
            # and its position
            if (A[j] < mn):
                mn = A[j]
                pos = j
  
        # Perform swaps if possible
        while (pos > i and count > 0 and 
             ((pos - 1, pos) not in mp)):
  
            # Insert current swap in hash
            mp.add((pos - 1, pos))
  
            A[pos], A[pos - 1] = A[pos - 1], A[pos]
            pos -= 1
            count -= 1
  
    # Print the required array
    for i in range(0, n):
        print(A[i], end = " ")
  
# Driver code
A = [ 2, 1, 4, 3, 6, 5 ]
n = len(A)
  
findSmallestArray(A, n)
  
# This code is contributed by Sanjit_Prasad

1 2 3 4 5 6

Complejidad del tiempo: O(N ² )