Lexicographically smallest permutation of [ 1 , N ] based on given Binary string | Function to generate the lexicographically smallest permutation according to the given criteria ; Stores the resultant permutation ; Initialize the first elements to 1 ; Traverse the given string S ; Number greater than last number ; Number equal to the last number ; Correct all numbers to the left of the current index ; Printing the permutation ; Driver Code
def constructPermutation ( S , N ) : NEW_LINE INDENT ans = [ 0 ] * N NEW_LINE ans [ 0 ] = 1 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT if ( S [ i - 1 ] == '0' ) : NEW_LINE INDENT ans [ i ] = i + 1 NEW_LINE DEDENT else : NEW_LINE INDENT ans [ i ] = ans [ i - 1 ] NEW_LINE DEDENT for j in range ( i ) : NEW_LINE INDENT if ( ans [ j ] >= ans [ i ] ) : NEW_LINE INDENT ans [ j ] += 1 NEW_LINE DEDENT DEDENT DEDENT for i in range ( N ) : NEW_LINE INDENT print ( ans [ i ] , end = " " ) NEW_LINE if ( i != N - 1 ) : NEW_LINE INDENT print ( " ▁ " , end = " " ) NEW_LINE DEDENT DEDENT DEDENT S = "100101" NEW_LINE constructPermutation ( S , len ( S ) + 1 ) NEW_LINE