World's most popular travel blog for travel bloggers.

# restricted sub-permutations check

, ,
Problem Detail:

I am solving the following problem, motived by combinatorial optimization sampling proces.

I have restriction (0,1) matrix to restrict which item (column index) can be on current position (row index) at permutations. For example: 4x4 case (4 position permutations)

 1     1     1     0  1     1     0     1  1     0     1     1  0     1     1     1 

So, on position 4 (4th row at restriction matrix) is not allowed items 1, for example.

This restrictions produce the following list of possible permutations (earch row is one possible permutation):

 1     2     3     4  1     2     4     3  1     4     3     2  2     1     3     4  2     1     4     3  2     4     1     3  3     1     4     2  3     2     1     4  3     4     1     2 

I am looking for algorithm to check if any sub-permutation, which is represented by first N < 4 positions, may correspond to any of possible permutation or not, without need to avaluate all possible permutations.

For example sub-permutation [1 2 3] is OK, but sub-permutation [3 4 2] is not.

###### Answered By : Yuval Filmus

A sub-permutation (not necessarily initial) corresponds to the removal of rows and columns in your restriction matrix. So your problem can be reduced to the case $N = 0$ (you also have to check that your sub-permutation conforms to the restriction matrix). In order to determine whether a restriction matrix admits any permutation, treat it as an $n \times n$ bipartite graph, and check whether the graph has a perfect matching.

Here is an example. Consider your restriction matrix $$\begin{matrix} 1&1&1&0 \\ 1&1&0&1 \\ 1&0&1&1 \\ 0&1&1&1 \end{matrix}$$ Choosing the first three elements to be $1,2,3$ is the same as deleting the first three rows and columns. We get $\begin{matrix} 1 \end{matrix}$, which has a perfect matching as a $1\times 1$ bipartite graph.

In contrast, choosing the first three elements to be $3,4,2$ is the same as deleting the first three rows (say) and columns $3,4,2$ (rows and columns might be switched depending on the representation). We get $\begin{matrix} 0 \end{matrix}$, which doesn't have a perfect matching.