Determining orders from binary matrix denoting allowed positions

Question

So given a square binary matrix of n-dimensions where a 1 would indicate that an entity can exist in that position and a 0 would indicate it cannot exist in that position, my question is; is their an efficient algorithm to determine possible orders of the set, if each entity can only be in one position in the final order(s) and the final order(s) must use each entity.

For example, the top row is the entity name and the first column is the position number, given this matrix:

$$A = \begin{array}{l|llllll} & a& b& c& d& e& f\\ \hline 1& 1& 0& 1& 0& 0& 0\\ 2& 1& 1& 0& 1& 0& 0\\ 3& 1& 1& 1& 1& 0& 0\\ 4& 0& 1& 0& 1& 0& 1\\ 5& 0& 0& 1& 1& 1& 1\\ 6& 0& 0& 0& 1& 1& 1\\ \end{array} $$

One example of a possible order is

a - b - c - d - e - f

and

c - a - b - d - e - f

Using an algorithm based on permanents of binary matrices, I can determine that there is a total 20 possible successful orders for this particular matrix. Without brute forcing all possible permutations, is there a way to efficiently determine what each possible order is.

Answer 1

One way to represent your problem is by a bipartite perfect matching between your "entities", e.g. $\{a,b,c,d,e,f\}$, and their positions in an "order", e.g. $\{1,2,3,4,5,6\}$.

Here those entities and positions form the two (equal size) "parts" of the vertices $V$. The allowed positions for each entity define the edges $E$ of this bipartite graph $G=(V,E)$. The binary matrix $A$ from your Question is sometimes called the biadjacency matrix of $G$.

Generating all the possible orders thus amounts to the problem of finding all perfect matchings in the bipartite graph $G$.

There is a good bit of literature on how to improve on a naive approach ("brute force") to find all these perfect matchings. I wonder if the effort to implement the algorithm with the best known asymptotic performance would be worthwhile to you. T. Uno ($2001$) proposes A Fast Algorithm for Enumerating Bipartite Perfect Matchings, a sophisticated method that achieves $O(|V|^{1/2} |E| + N_p \log |V|)$ time, where $N_p$ is the actual number of bipartite perfect matchings that exist. In other words its "amortized cost" per matching to be found is only $O(\log |V|)$.

---

For an easier implementation that still improves on the most naive approach, consider simply arranging your entities by increasing "degrees" (number of allowed positions). This tends to trim the "tree" of dependent choices earlier and avoid more "dead-end" searches than a random selection of entities.

Thus in the example outlined in the Question, a search for perfect matchings would begin with entity $e$ since this has degree $2$ (only two allowed positions). Once the position of entity $e$ is chosen, there are only two allowed positions remaining for entity $f$, etc.