Background
$\newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak S}\newcommand\mfm[1]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{2}}}\def\pth{\color{#6c0}{\mfm{3}}}\def\pf{4}\def\pv{\color{#999}5}\def\gr{\color{#ccc}}\let\ss\gr$Suppose I have two identical batches of $n$ marbles. Each marble can be one of $c$ colors, where $c≤n$. Let $n_i$ denote the number of marbles of color $i$ in each batch.
Let $\msS$ be the multiset $\small\{\overbrace{\po,…,\po}^{n_1},\;\overbrace{\pt,…,\pt}^{n_2},\;…,\;\overbrace{\vphantom 1\pc,…,\pc}^{n_c}\}$ representing one batch. In frequency representation, $\msS$ can also be written as $(\po^{n_1} \;\pt^{n_2}\; … \;\pc^{n_c})$.
The number of distinct permutations of $\msS$ is given by the multinomial: $$\left|\mfS_{\msS}\right|=\binom{n}{n_1,n_2,\dots,n_c}=\frac{n!}{n_1!\,n_2!\cdots n_c!}=n! \prod_{i=1}^c \frac1{n_i!}.$$
Question
Is there an efficient algorithm to generate two diffuse, deranged permutations $P$ and $Q$ of $\msS$ at random? (The distribution should be uniform.)
A permutation $P$ is diffuse if for every distinct element $i$ of $P$, the instances of $i$ are spaced out roughly evenly in $P$.
For example, suppose $\msS=(\po^4\;\pt^4)=\{\po,\po,\po,\po,\pt,\pt,\pt,\pt\}$.
- $\{\po, \po, \po, \pt, \pt, \pt, \pt, \po\}$ is not diffuse
- $\{\po, \pt, \po, \pt, \po, \pt, \po, \pt\}$ is diffuse
More rigorously:
- If $n_i=1$, there is only one instance of $i$ to “space out” in $P$, so let $\Delta(i)=0$.
- Otherwise, let $d(i,j)$ be the distance between instance $j$ and instance $j+1$ of $i$ in $P$. Subtract from it the expected distance between instances of $i$, defining the following: $$\delta(i,j)=d(i,j)-\frac n{n_i}\qquad\qquad\Delta(i)=\sum_{j=1}^{n_i-1} \delta(i,j)^2$$ If $i$ is evenly spaced in $P$, then $\Delta(i)$ should be zero, or very close to zero if $n_i\nmid n$.
Now define the statistic $s(P)=\sum_{i=1}^c\Delta(i)$ to measure how much every $i$ is evenly spaced in $P$. We call $P$ diffuse if $s(P)$ is close to zero, or roughly $s(P)\ll n^2$. (One can choose a threshold $k\ll1$ specific to $\msS$ so that $P$ is diffuse if $s(P)<kn^2$.)
This constraint recalls a stricter real-time scheduling problem called the pinwheel problem with multiset $\ms A=n/\msS$ (so that $a_i=n/n_i$) and density $\rho=\sum_{i=1}^c n_i/n=1$. The objective is to schedule a cyclic infinite sequence $P$ such that any subsequence of length $a_i$ contains at least one instance of $i$. In other words, a feasible schedule requires all $d(i,j)≤a_i$; if $\ms A$ is dense ($\rho= 1$), then $d(i,j)=a_i$ and $s(P)=0$. The pinwheel problem appears to be NP-complete.
Two permutations $P$ and $Q$ are deranged if $P$ is a derangement of $Q$; that is, $P_i ≠ Q_i$ for every index $i\in[n]$.
For example, suppose $\msS=(\po^2\;\pt^2)=\{\po,\po,\pt,\pt\}$.
- $\{\po, \pt, \po, \pt\}$ and $\{\po, \po, \pt, \pt\}$ are not deranged
- $\{\po, \pt, \po, \pt\}$ and $\{\pt, \po, \pt, \po\}$ are deranged
Exploratory analysis
I am interested in the family of multisets with $n=20$ and $n_i=4$ for $i\lesssim4$. In particular, let $\msD=(\gr1^4\,\gr2^4\,\gr3^4\,\gr4^3\,\gr5^2\,\gr6^1\,\gr7^1\,\gr8^1)$.
The probability that two random permutations $P$ and $Q$ of $\msD$ are deranged is about 3%.
This can be calculated as follows, where $L_k$ is the $k$th Laguerre polynomial: \begin{align*} \left|{\mathfrak D}_{\msD}\right| &=\int_0^\infty \!\!dt\; e^{-t}\, \prod_{i=1}^c L_{n_i}(t) =\int_0^\infty \!\!dt\; e^{-t}\, \bigl(L_4(t)\bigr)^3\bigl(L_3(t)\bigr)\bigl(L_2(t)\bigr)\bigl(L_1(t)\bigr)^3\\ &=4.5\times10^{11}\\ \left|\mfS_{\msD}\right| &=n!\prod_{i=1}^c \frac1{n_i!} =\frac{20!}{(4!)^3\,(3!)\,(2!)\,(1!)^3} =1.5\times10^{13}\\ p&=\left|{\mathfrak D}_{\msD}\right|/ \left|\mfS_{\msD}\right|\approx0.03\end{align*} See here for an explanation.
The probability that a random permutation $P$ of $\msD$ is diffuse is about 0.01%, setting the arbitrary threshold at roughly $s(P)<25$.
Below is an empirical probability plot of 100,000 samples of $s(P)$ where $P$ is a random permutation of $\msD$.
At medium sample sizes, $s(P)\sim \text{Gamma}(\alpha\approx8,\beta\approx18)$.
\begin{array}{ccl}\renewcommand\mfm[1]{\textbf{#1}} \hline P & s(P) & \text{cdf}(s(P)) \\ \hline \{\po, \ss8, \pt, \pth, \pf, \po, \pv, \pt, \pth, \ss6, \po, \pf, \pt, \pth, \ss7, \po, \pv, \pt, \pf, \pth\} & \frac{11}9\approx1\, & <10^{-5} \\ \{\ss8, \pt, \pth, \pf, \po, \ss6, \pv, \pt, \pth, \pf, \po, \ss7, \po, \pt, \pth, \pv, \pf, \po, \pt, \pth\} & \frac{140}9\approx16 & <10^{-4} \\ \{\pth, \ss6, \pv, \po, \pth, \pf, \pt, \po, \pt, \ss7, \ss8, \pv, \pt, \pf, \po, \pth, \pth, \pt, \po, \pf\} & \frac{650}9\approx72 & \phantom{<1}0.05 \\ \{\pth, \po, \pth, \pf, \ss8, \pt, \pt, \po, \po, \pv, \pth, \pth, \pt, \ss6, \pf, \pf, \pt, \po, \ss7, \pv\} & \frac{1223}9\approx136 & \phantom{<1}0.45 \\ \{\pf, \po, \po, \pf, \pv, \pv, \po, \pth, \pth, \ss7, \po, \pt, \pt, \pf, \pth, \pth, \ss8, \pt, \pt, \ss6\} & \frac{1697}9\approx189 & \phantom{<1}0.80 \\ \hline \end{array}
The probability that two random permutations are valid (both diffuse and deranged) is around $v\approx(0.03)(0.0001)^2\approx10^{-10}$.
Inefficient algorithms
A common “fast” algorithm to generate a random derangement of a set is rejection-based:
do
P ← random_permutation(D)
until is_derangement(D, P)
return P
which takes approximately $e$ iterations, since there are roughly $n!/e$ possible derangements. However a rejection-based randomized algorithm would not be efficient for this problem, as it would take on the order of $1/v\approx10^{10}$ iterations.
In the algorithm used by Sage, a random derangement of a multiset “is formed by choosing an element at random from the list of all possible derangements.” Yet this too is inefficient, as there are $v\,|\mfS_{\msD}|^2\approx10^{16}$ valid permutations to enumerate, and besides, one would need an algorithm just to do that anyway.
Further questions
What is the complexity of this problem? Can it be reduced to any familiar paradigm, such as network flow, graph coloring, or linear programming?
