Lexicographic ranking and unranking of derangements in cycle notation
We present lexicographic ranking and unranking algorithms for derangements expressed in cycle notation. These algorithms run in O(nlogn) O ( n log n ) time, require O(n) O ( n ) space, and use O(n) O ( n ) arithmetic operations. Similar algorithms that require less than or equal to O(nlogn) O ( n log n ) time with O(n) O ( n ) space complexity have not previously been proposed.
ranking unranking derangements algorithm combinatorial problem