Smallest Derangement of Sequence | Java program to generate smallest derangement using priority queue . ; Generate Sequence and insert into a priority queue . ; Generate Least Derangement ; Print Derangement ; Driver code
import java . util . * ; class GFG { static void generate_derangement ( int N ) { int [ ] S = new int [ N + 1 ] ; PriorityQueue < Integer > PQ = new PriorityQueue < > ( ) ; for ( int i = 1 ; i <= N ; i ++ ) { S [ i ] = i ; PQ . add ( S [ i ] ) ; } int [ ] D = new int [ N + 1 ] ; for ( int i = 1 ; i <= N ; i ++ ) { int d = PQ . peek ( ) ; PQ . remove ( ) ; if ( d != S [ i ] i == N ) { D [ i ] = d ; } else { D [ i ] = PQ . peek ( ) ; PQ . remove ( ) ; PQ . add ( d ) ; } } if ( D [ N ] == S [ N ] ) { int t = D [ N - 1 ] ; D [ N - 1 ] = D [ N ] ; D [ N ] = t ; } for ( int i = 1 ; i <= N ; i ++ ) System . out . printf ( " % d ▁ " , D [ i ] ) ; System . out . printf ( "NEW_LINE"); } public static void main ( String [ ] args ) { generate_derangement ( 10 ) ; } }