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