Largest Derangement of a Sequence | Python3 program to find the largest derangement ; Stores result ; Insert all elements into a priority queue ; Fill Up res [ ] from left to right ; New Element poped equals the element in original sequence . Get the next largest element ; If given sequence is in descending order then we need to swap last two elements again ; Driver code
def printLargest ( seq , N ) : NEW_LINE INDENT res = [ 0 ] * N NEW_LINE pq = [ ] NEW_LINE for i in range ( N ) : NEW_LINE INDENT pq . append ( seq [ i ] ) NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT pq . sort ( ) NEW_LINE pq . reverse ( ) NEW_LINE d = pq [ 0 ] NEW_LINE del pq [ 0 ] NEW_LINE if ( d != seq [ i ] or i == N - 1 ) : NEW_LINE INDENT res [ i ] = d NEW_LINE DEDENT else : NEW_LINE INDENT res [ i ] = pq [ 0 ] NEW_LINE del pq [ 0 ] NEW_LINE pq . append ( d ) NEW_LINE DEDENT DEDENT if ( res [ N - 1 ] == seq [ N - 1 ] ) : NEW_LINE INDENT res [ N - 1 ] = res [ N - 2 ] NEW_LINE res [ N - 2 ] = seq [ N - 1 ] NEW_LINE DEDENT print ( " Largest ▁ Derangement " ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT print ( res [ i ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT seq = [ 92 , 3 , 52 , 13 , 2 , 31 , 1 ] NEW_LINE n = len ( seq ) NEW_LINE printLargest ( seq , n ) NEW_LINE