4
$\begingroup$

I am looking for an algorithm that generates a derangement with uniform probability across all possible derangements.

This is similar to Generating a random derangement, but with the requirement that the randomness is unbiased, i.e. every derrangment has equal opportunity of being selected.

I have tried the algorithm described here and here, but they offer no such claim, and do not seem to be able to generate every derangement. For example, it does not generate (2,1,4,5,3).

$\endgroup$
2
  • $\begingroup$ Are you allowed to use a rand function for that matter? $\endgroup$ Dec 24, 2014 at 7:46
  • $\begingroup$ @barakmanos, yes, if not, it would be impossible. $\endgroup$ Dec 24, 2014 at 7:47

2 Answers 2

3
$\begingroup$

The algorithm described in the first of your two quoted links can produce $(2,1,4,5,3)$ without any problem: $\require{enclose}$ $$\begin{matrix} 1 & 2 & 3 & 4 & 5\\ 1 & 2 & \underline5 & 4 & \underline3\\ 1 & 2 & 5 & 4 & 3\\ 1 & 2 & \underline4 & \underline5 & 3\\ 1 & 2 & \enclose{circle}{4} & 5 & 3\\ \underline{2} & \underline1 & \enclose{circle}{4} & 5 & 3\\ \end{matrix}$$

  1. initial state,
  2. $3\leftrightarrow5$,
  3. $p\ge\frac{4D_3}{D_5}$, marks nothing,
  4. $4\leftrightarrow5$,
  5. $p\lt\frac{3D_2}{D_4}$, marks $\enclose{circle}{4}$,
  6. $1\leftrightarrow2$
$\endgroup$
0
$\begingroup$

My first thought is that derangements are like perfect matchings in a very dense bipartite graph. If you are not familiar with the concept of bipartite graphs or matchings, this might be unnecessarily confusing.

Given a set $[n] = \lbrace 1, \dots, n \rbrace$, consider a bipartite graph $G$ with $n$ vertices $l_{1},\dots, l_{n}$ on the left and $n$ vertices $u_{1},\dots, u_{n}$ on the right, with $l_{i}$ being connected with all vertices on the right except the $u_{i}$. You could think that vertex $l_{i}$ corresponds to the $i$th position of the desired derangement, while $u_{j}$ corresponds to value $j$: position $i$ can be assigned any value in $[n]$ except value $i$. A perfect matching in $G$ corresponds exactly to a derangement of $[n]$.

I found this article that points to $2$ papers that apparently describe a method to sample almost uniformly a perfect matching: https://cs.stackexchange.com/questions/10756/sampling-perfect-matching-uniformly-at-random Maybe you could check those. If not, maybe looking for algorithms to randomly sample perfect matchings from (dense) bipartite graphs could help expanding your search.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .