Smallest Derangement of Sequence | C # program to generate smallest derangement using priority queue . ; Generate Sequence and insert into a priority queue . ; Generate Least Derangement ; Print Derangement ; Driver code
using System ; using System . Collections . Generic ; class GFG { static void generate_derangement ( int N ) { int [ ] S = new int [ N + 1 ] ; List < int > PQ = new List < int > ( ) ; for ( int i = 1 ; i <= N ; i ++ ) { S [ i ] = i ; PQ . Add ( S [ i ] ) ; } int [ ] D = new int [ N + 1 ] ; PQ . Sort ( ) ; for ( int i = 1 ; i <= N ; i ++ ) { PQ . Sort ( ) ; int d = PQ [ 0 ] ; PQ . RemoveAt ( 0 ) ; if ( d != S [ i ] i == N ) { D [ i ] = d ; } else { PQ . Sort ( ) ; D [ i ] = PQ [ 0 ] ; PQ . RemoveAt ( 0 ) ; 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 ++ ) Console . Write ( D [ i ] + " ▁ " ) ; Console . Write ( " STRNEWLINE " ) ; } public static void Main ( String [ ] args ) { generate_derangement ( 10 ) ; } }