# restricted sub-permutations check

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.

• Potentially related question. (Oh, that was you. I see that these things still busy you, nice!) – Raphael Feb 3 '16 at 12:00
• Yes ... still here :) – michal Feb 3 '16 at 12:11
• I'm confused by what you are asking. What do you mean by a sub-permutation? Can you define what "correspondence" you are thinking of, more precisely? When does a subpermutation correspond to a permutation? – D.W. Feb 3 '16 at 17:38

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.