1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Potentially related question. (Oh, that was you. I see that these things still busy you, nice!) $\endgroup$ – Raphael Feb 3 '16 at 12:00
  • $\begingroup$ Yes ... still here :) $\endgroup$ – michal Feb 3 '16 at 12:11
  • $\begingroup$ 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? $\endgroup$ – D.W. Feb 3 '16 at 17:38
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Probably my description is not clear. In my problem I have only restriction matrix and testing sub-permutation. I need to know if the given sub-permutation correspond any possible full permutation or not. $\endgroup$ – michal Feb 3 '16 at 11:46
  • $\begingroup$ I added an example corresponding to yours. I believe you haven't understood my solution. $\endgroup$ – Yuval Filmus Feb 3 '16 at 11:50
  • $\begingroup$ Yes ... your example is completely clear. Thanks! $\endgroup$ – michal Feb 3 '16 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.