# Uniformly Generating Derangements with Fixed Number of Cycles in Polynomial Time

## Discrete and Computational Geometry, Graphs, and Games

## Keywords:

derangement, random generation, dynamic programming, polynomial time algorithm## 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.

## Downloads

## Published

## How to Cite

*Thai Journal of Mathematics*,

*21*(4), 899–915. Retrieved from https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1555