Smallest Derangement of Sequence | Python3 program to generate smallest derangement using priority queue . ; Generate Sequence and insert into a priority queue . ; Generate Least Derangement ; Print Derangement ; Driver code
def generate_derangement ( N ) : NEW_LINE INDENT S = [ i for i in range ( N + 1 ) ] NEW_LINE PQ = [ ] NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT PQ . append ( S [ i ] ) NEW_LINE DEDENT D = [ 0 ] * ( N + 1 ) NEW_LINE PQ . sort ( ) NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT PQ . sort ( ) NEW_LINE d = PQ [ 0 ] NEW_LINE del PQ [ 0 ] NEW_LINE if ( d != S [ i ] ) or ( i == N ) : NEW_LINE INDENT D [ i ] = d NEW_LINE DEDENT else : NEW_LINE INDENT PQ . sort ( ) NEW_LINE D [ i ] = PQ [ 0 ] NEW_LINE del PQ [ 0 ] NEW_LINE PQ . append ( d ) NEW_LINE DEDENT DEDENT if D [ N ] == S [ N ] : NEW_LINE INDENT t = D [ N - 1 ] NEW_LINE D [ N - 1 ] = D [ N ] NEW_LINE D [ N ] = t NEW_LINE DEDENT for i in range ( 1 , N + 1 ) : NEW_LINE INDENT print ( D [ i ] , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT generate_derangement ( 10 ) NEW_LINE