Lexicographically smallest permutation of length 2 N that can be obtained from an N | Python3 program for the above approach ; Function to find the lexicographically smallest permutation of length 2 * N satisfying the given conditions ; Stores if i - th element is placed at odd position or not ; Traverse the array ; Mark arr [ i ] true ; Stores all the elements not placed at odd positions ; Iterate in the range [ 1 , 2 * N ] ; If w [ i ] is not marked ; Stores whether it is possible to obtain the required permutation or not ; Stores the permutation ; Traverse the array arr [ ] ; Finds the iterator of the smallest number greater than the arr [ i ] ; If it is S . end ( ) ; Mark found false ; Push arr [ i ] and * it into the array ; Erase the current element from the Set ; If found is not marked ; Otherwise , ; Print the permutation ; Driver Code ; Given Input ; Function call
from bisect import bisect_left NEW_LINE def smallestPermutation ( arr , N ) : NEW_LINE INDENT w = [ False for i in range ( 2 * N + 1 ) ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT w [ arr [ i ] ] = True NEW_LINE DEDENT S = set ( ) NEW_LINE for i in range ( 1 , 2 * N + 1 , 1 ) : NEW_LINE INDENT if ( w [ i ] == False ) : NEW_LINE INDENT S . add ( i ) NEW_LINE DEDENT DEDENT found = True NEW_LINE P = [ ] NEW_LINE S = list ( S ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT it = bisect_left ( S , arr [ i ] ) NEW_LINE if ( it == - 1 ) : NEW_LINE INDENT found = False NEW_LINE break NEW_LINE DEDENT P . append ( arr [ i ] ) NEW_LINE P . append ( S [ it ] ) NEW_LINE S . remove ( S [ it ] ) NEW_LINE DEDENT if ( found == False ) : NEW_LINE INDENT print ( " - 1" ) NEW_LINE DEDENT else : NEW_LINE INDENT for i in range ( 2 * N ) : NEW_LINE INDENT print ( P [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 4 , 1 , 3 ] NEW_LINE N = len ( arr ) NEW_LINE smallestPermutation ( arr , N ) NEW_LINE DEDENT