1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As I commented on your earlier Question, Wikipedia says computing the permanent "is known to be more difficult than the computation of the determinant of a matrix... The development of both exact and approximate algorithms for computing the permanent of a matrix is an active area of research." That pertains, of course, to counting how many possible orders there are. Here you seem more interested in generating each possible order. $\endgroup$ – hardmath Apr 26 '17 at 22:29
  • $\begingroup$ Yeah as I'm working on this task I realise the severe computational time of attempting to determine this result, I'm kind of doing this to get ideas such as your answer below which I have immediately started looking at. $\endgroup$ –  Bodmas12 Apr 27 '17 at 3:26
0
$\begingroup$

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.

$\endgroup$

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.