Uniformly Generating Derangements with Fixed Number of Cycles in Polynomial Time

Discrete and Computational Geometry, Graphs, and Games

Abstract

We study the uniform sampling of permutations without fixed points, i.e., derangements, that can be decomposed into $m$ disjoint cycles. Since the number of cycles in a random derangement tends towards the standard distribution, rejection sampling may take exponential time when $m$ largely deviates from the mean of $\Theta(\log n)$. We propose an algorithm for generating a uniformly random derangement of $n$ items with $m$ cycles in $O(n^{2.5}\log n)$ time complexity using dynamic programming with an assumption that all arithmetic operations can be done in time $O(1)$. Taking into account the arithmetic operations on large integers, the running time becomes $O(n^{3.5}\log^3 n)$. Our algorithm uses permutation types to structure our uniform generation of derangements.