Generate Least Derangement
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