Algorithm that finds permutation of rows and colums that decomposises a matrix of 0 and 1 into minimal and exclusive set of covering rectangles
The task is to find a permutation of rows and columns of the matrix, such that a matrix built by shuffling the columns and rows according to the permutations can be partitioned into a minimal set of rectangles. Find all the rectangles as well.
For illustration, one can think about the problem this way:
Suppose I have a set of objects and a set of properties. Each object can have any number of (distinct) properties. The task is to summarize (report) this mapping using the least amount of sentences. Each sentence has a form "
<list of objects> have properties <list of properties>
".
Brute-force the solution by applying the permutations and run the algorithm on each try have complexity that explodes exponentially making this approach non-practical for matrices bigger than 15×15.
This problem feels like it is NP-hard, and there might be no fast (polynomial in time) solutions. What I present here is a heuristicall approximation, that is polinomial in time O(n^2) and good enough for my purposes.
It is worth noting that the problem is symmetric with respect to swapping rows with columns (features with objects).
Input: binary matrix, where rows are objects and columns are features and ones in the matrix represent matched pairs (object, feature).
The algorithm will take several steps.
Unshuffling rows are independent of unshuffling columns and both tasks can be run separately (concurrently). Let us assume I am looking for the unshuffling permutation of columns.
Also, it is worth noting, that unshuffling a matrix should yield the same results if we swap ones with zeroes.
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.