Lexicographically smallest permutation number up to K having given array as a subsequence | Function to find the lexicographically smallest permutation such that the given array is a subsequence of it ; Stores the missing elements in arr in the range [ 1 , K ] ; Stores if the ith element is present in arr or not ; Loop to mark all integers present in the array as visited ; Loop to insert all the integers not visited into missing ; Append INT_MAX at end in order to prevent going out of bounds ; Pointer to the current element ; Pointer to the missing element ; Stores the required permutation ; Loop to construct the permutation using greedy approach ; If missing element is smaller that the current element insert missing element ; Insert current element ; Print the required Permutation ; Driver Code ; Function Call
def findPermutation ( K , arr ) : NEW_LINE INDENT missing = [ ] NEW_LINE visited = [ 0 ] * ( K + 1 ) NEW_LINE for i in range ( 4 ) : NEW_LINE INDENT visited [ arr [ i ] ] = 1 NEW_LINE DEDENT for i in range ( 1 , K + 1 ) : NEW_LINE INDENT if ( not visited [ i ] ) : NEW_LINE INDENT missing . append ( i ) NEW_LINE DEDENT DEDENT INT_MAX = 2147483647 NEW_LINE arr . append ( INT_MAX ) NEW_LINE missing . append ( INT_MAX ) NEW_LINE p1 = 0 NEW_LINE p2 = 0 NEW_LINE ans = [ ] NEW_LINE while ( len ( ans ) < K ) : NEW_LINE INDENT if ( arr [ p1 ] < missing [ p2 ] ) : NEW_LINE INDENT ans . append ( arr [ p1 ] ) NEW_LINE p1 = p1 + 1 NEW_LINE DEDENT else : NEW_LINE INDENT ans . append ( missing [ p2 ] ) NEW_LINE p2 = p2 + 1 NEW_LINE DEDENT DEDENT for i in range ( 0 , K ) : NEW_LINE INDENT print ( ans [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT K = 7 NEW_LINE arr = [ 6 , 4 , 2 , 1 ] NEW_LINE findPermutation ( K , arr ) NEW_LINE DEDENT