Random uniform sampling of position restricted permutations

Question

Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions?

Consider $N \times N$ restriction matrices $R$, that is matrices over $\{0,1\}$. Each such $R$ defines a set of permutations $\Pi_R$ according to

$\qquad\displaystyle \pi \in \Pi_R \iff \forall i \in [1..n].\ \pi(i) = j \implies R_{i,j} = 1$.

Note that $R$ is not permutation matrix but a general restriction matrix. I want to sample uniformly from $\Pi_R$ given $R$.

So far I am using Hungarian's assignment algorithm to produce random permutations consistent with restriction matrix $R$, but these permutations are significantly non-uniformly sampled.

Examples:

• Every $R$ that has one one per row and column admits only a single permutation.

• For

  $\qquad\displaystyle R = \left( \begin{array}{ccc} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right) $

  there are only two permutations: $\pi_1 = (2 1 3)$ and $\pi_2 = (2 3 1)$.

• If $R$ contains only ones, $\Pi_R$ is the set of all permutations.

Answer 1

I'll answer both the question as it currently stands, and the original version of the question.

The current question

Your question is basically asking for a way to sample uniformly at random from the set of perfect matchings of a given bipartite graph. In particular, we have $N$ nodes on the left side corresponding to the $N$ rows of $R$, and $N$ nodes on the right side corresponding to the $N$ columns of $R$. Draw an edge between node $i$ (on the left) and node $j$ (on the right) when $R_{i,j}=1$. This gives a bipartite graph $G$. Now there's a bijection between the perfect matchings of $G$ and the permutations in $\Pi_R$, so we want to sample uniformly at random from the perfect matchings of $G$.

The following question refers to algorithm for exactly that problem: Sampling perfect matching uniformly at random. In particular, there are existing algorithms that approximate sampling from the uniform distribution (i.e., their distribution is almost uniform).

The original question

Originally, the question imposed the stronger restriction that $\pi(i)=j \Longleftrightarrow R_{i,j}=1$. Here's the solution to that version of the problem.

Theorem. If $R$ is a permutation matrix, there is a single permutation $\pi$ that is compatible with $R$. If $R$ is not a permutation matrix, there is no permutation $\pi$ that is compatible with $R$.

Recall that a permutation matrix is a matrix that has exactly one 1 in every row and every column.

Proof of theorem. Consider any row, say row $i$. If it is all zeros (has no $1$), then there's no matching permutation ($\pi(i)$ has to equal something). If it has two or more $1$'s, there is no matching permutation (you can't have $\pi(i)=j$ and $\pi(i)=k$ where $j\ne k$). So for there to be a matching permutation, the row must have exactly one $1$. Since the row $i$ was arbitrary, this must be true of all rows. By symmetric, the same is true for all columns. QED.

---

You can easily recognize whether a matrix is a permutation matrix or not. Given a permutation matrix you can easily recover the corresponding permutation. Therefore, an algorithm to do what you want is trivial. The algorithm either outputs nothing (if $R$ is not a permutation matrix) or always deterministically outputs a single permutation (if $R$ is a permutation matrix).

---

For the example $3 \times 3$ matrix you gave in your question, there is no permutation that is consistent with that matrix. Your matrix has $R_{2,1}=1$ and $R_{2,2}=1$. By your conditions, this implies the requirements that $\pi(2)=1$ and $\pi(2)=2$. However, $1\ne 2$, so it is impossible to have a permutation $\pi$ that satisfies both of these requirements.