Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

decomposing binary matrices

by hv (Prior)
on Feb 16, 2007 at 13:01 UTC ( [id://600418]=perlquestion: print w/replies, xml ) Need Help??

hv has asked for the wisdom of the Perl Monks concerning the following question:

Update: this is now solved, see Re^2: decomposing binary matrices (2).

Given a set of variables and a set of values, with the property that each variable has a distinct value, we can get a matrix of booleans summarising the possibilities (such that a value of 1 means "possible", 0 means "not possible"):
ABCDE
100110
210111
301010
411001
501110

With those constraints, we can derive additional information: since A and E are restricted to only two values between them, they must consume those two values; effectively we can split the above matrix into two smaller matrices:
AE
211
411
BCD
1011
3101
5111

While this is relatively easy to do by eye with a small grid, I'm looking for an efficient algorithm to find such decompositions for larger grids, for both the case as in the example above where the number of variables is the same as the number of values, and for the case where there are more values than variables (so not all the values are used).

I'm not sure quite where to start looking, so suggestions for useful search terms would also be appreciated - I suspect that I should be treating the '1's in the matrix as edges in a graph, but quite what I'm looking for in the resulting graph I've not been able to characterise.

Hugo

Replies are listed 'Best First'.
Re: decomposing binary matrices
by BrowserUk (Patriarch) on Feb 16, 2007 at 15:01 UTC

    I think this does the job, but it needs testing on some more demanding sample data.

    c:\test>600418.pl This input 0 0 1 1 0 1 0 1 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 Inverted looks like this 0 : 01010 1 : 00111 2 : 11001 3 : 11101 4 : 01010 This subset can be removed from the main group: 0 : 01010 4 : 01010 c:\test>600418.pl This input 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 1 Inverted looks like this 0 : 00111 1 : 01010 2 : 00111 3 : 11001 4 : 11101 5 : 01010 6 : 01110 7 : 00111 This subset can be removed from the main group: 1 : 01010 5 : 01010 This subset can be removed from the main group: 0 : 00111 2 : 00111 7 : 00111

    Relating the subset numbering back to the pre-inversion set is left as an exercise.

    #! perl -slw use strict; =comment my @grid = ( [ 0, 0, 1, 1, 0 ], [ 1, 0, 1, 1, 1 ], [ 0, 1, 0, 1, 0 ], [ 1, 1, 0, 0, 1 ], [ 0, 1, 1, 1, 0 ], ); =cut my @grid = ( # 0 1 2 3 4 5 6 7 [ 0, 0, 0, 1, 1, 0, 0, 0, ], [ 0, 1, 0, 1, 1, 1, 1, 0, ], [ 1, 0, 1, 0, 1, 0, 1, 1, ], [ 1, 1, 1, 0, 0, 1, 1, 1, ], [ 1, 0, 1, 1, 1, 0, 0, 1, ], ); print "This input\n"; print "\t@$_" for @grid; my @inverted; for my $i ( 0 .. $#grid ) { $inverted[ $_ ] .= $grid[ $i ][ $_ ] for 0 .. $#{ $grid[ $i ] }; } print "\nInverted looks like this\n"; print "\t$_ : $inverted[ $_ ]" for 0 .. $#inverted; my @bitCounts; push @{ $bitCounts[ $inverted[ $_ ] =~ tr[1][1] ] }, $_ for 0 .. $#inv +erted; #print @{ $_||[] } for @bitCounts; for my $c ( 2 .. $#bitCounts ) { #print( "skipping $c elements < ${ \ scalar @{ $bitCounts[ $c ] } +} bits" ), next unless @{ $bitCounts[ $c ] } >= $c; my @set = @{ $bitCounts[ $c ] }; for my $offset ( 0 .. @set - $c ) { my $matches = grep{ $inverted[ $set[ $offset ] ] eq $_ } @inverted[ @set[ $offset .. $#set ] ]; #print "set:@set matches:$matches"; last unless $c <= $matches; print "\nThis subset can be removed from the main group:\n"; print "\t$_ : $inverted[ $_ ]" for grep{ $inverted[ $set[ $offset ] ] eq $inverted[ $_ ] } @set[ $offset .. $#set ]; } }

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      Thanks. First, I should note that there must be at least as many values as variables, since each variable must take a distinct value within the set of possible values.

      Second, variables that are part of an n-element submatrix need not have n bits set. The sparsest counterexample is:

      my @grid = ( # 0 1 2 3 4 5 [ 0, 0, 0, 1, 1, 0, ], [ 0, 0, 0, 1, 0, 1, ], [ 0, 0, 0, 0, 1, 1, ], [ 1, 1, 0, 0, 0, 0, ], [ 1, 0, 1, 0, 0, 0, ], [ 0, 1, 1, 0, 0, 0, ], );
      .. which can decompose into two 3-element submatrices.

      The least sparse version of that is:

      my @grid = ( # 0 1 2 3 4 5 [ 0, 0, 0, 1, 1, 1, ], [ 0, 0, 0, 1, 1, 1, ], [ 0, 0, 0, 1, 1, 0, ], [ 1, 1, 1, 1, 1, 1, ], [ 1, 1, 1, 1, 1, 1, ], [ 1, 1, 0, 1, 1, 1, ], );
      .. which can decompose the same way.

      Update: swapped 2 bits in the last row of the sparse matrix, so it actually represents what I'm saying

      Hugo

        Hm. Sorry to have wasted your time. I'd picked up on this bit of the OP

        ... since A and E are restricted to only two values between them, they must consume those two values;

        ... and hung my hat on it, but that obviously doesn't apply in the same way to the two examples above.

        Question: Would this example also decompose into the (same?) two groups as the above?

        my @grid = ( [ 0, 1, 0, 1, 0, 0, ], [ 0, 0, 0, 1, 1, 0, ], [ 0, 1, 0, 0, 1, 0, ], [ 1, 0, 0, 0, 0, 1, ], [ 1, 0, 1, 0, 0, 0, ], [ 1, 0, 0, 0, 0, 1, ], );

        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
Re: decomposing binary matrices
by Herkum (Parson) on Feb 16, 2007 at 14:10 UTC

    Have you take a look at Graph? If that does not help then you can get Mastering Algorithms with Perl. I got it recently and I found that it very accessible to someone who did not have much math knowledge (that would be me! :) ).

      Thanks, I tried drawing the graph on a piece of paper, and while I'm not yet sure I think it may be possible to say that: the graph for any undecomposable submatrix has a cycle that traverses all its nodes; and that: the nodes in the longest cycle form the largest undecomposable submatrix. Thus from the example in the OP, you can get cycles A-2-E-4-A and B-3-C-1-D-5-B, but there is no cycle looping through all 10 of the nodes.

      That does not immediately help, since Graph will only find "the first cycle" - I can't tell from the docs (nor from a brief look at the code), but I suspect that since all my edges are undirected, it will just immediately return (eg) A-2-A as a cycle - but this concept may well help me search for an algorithm.

      Update: this page tells me:

      Finding the longest cycle in a graph includes the special case of Hamiltonian cycle (see gif), so it is NP-complete.
      Damn.

      Hugo

        That was the reason I suggested the Mastering Algorithms with Perl book. It dealt quite a few algorithms and devotes a chapter to matrices. It also goes into great detail for several different methods for using Graph.

        Graph by itself is not very useful because it is expected that you know what your are doing, which I find frustrating when I encounter a problem. But there is a lot more to it than first appearances would suggest.

Re: decomposing binary matrices
by blokhead (Monsignor) on Feb 16, 2007 at 17:24 UTC
    As I suggested in the CB, if your ultimate goal is only to find an assignment of values to variables that meets all the constraints, then you don't have to actually decompose the matrix. All you need to do is find a perfect bipartite matching.

    A bipartite graph is a graph where the vertices are partitioned into 2 sets, and every edge crosses between these sets (i.e, does not stay within a set). In this case, one set denotes your variables and the other set denotes your values. Draw an edge between a variable and a value if it is legal to assign that value to that variable.

    A matching is a subset of edges from a graph, where no two edges share an endpoint. Since all edges in a bipartite graph run between these 2 sets, you can think of a matching as a (partial) mapping from 1 set to the other (each vertex in set A is paired with at most 1 vertex in set B). In this case, it represents a mapping from variables to values. Since the matching is a subset of the available edges, the mapping doesn't include any assignments that you have deemed "illegal".

    What you want is a perfect matching, one that covers all vertices (so it's a 1-to-1 mapping between variables and values). Usually this problem is phrased as the "marriage problem" -- The two sets of vertices are men & women, and there is an edge between a man & a woman if they could be happy married. You want to know if there is a way to pair them up so that each couple is happy (and if there is such a way to pair them up, output it).

    An example that I found with pictures is here: bipartite matching. Googling for bipartite matching algorithm turns up plenty of hits. I know that there are efficient algorithms for doing it, but can't remember all of the details.

    blokhead

      Thanks, these are useful terms and concepts for me.

      I'm not looking for a perfect match - that would correspond to "a possible assignment". I'm looking for information encapsulating the set of all perfect matches.

      One interpretation of that is that if I represent the 5x5 matrix of my OP as a bipartite graph, I'm looking for the edges that are missing from every perfect match, since I can delete them. Deleting those edges would effectively split the graph into connected subgraphs (corresponding to the 2x2 and 3x3 submatrices in the OP).

      In short, I'm looking to use the constraint "each variable has a distinct value" to reduce the number of 1s in the matrix.

      In practice, I think it would simplify visualisation and make further work more efficient if the resulting discrete subgraphs/submatrices were separated, but I do not think that is in principle necessary - the job is to maximise the information extracted from the constraint. In the example, the constraint tells me that each of the assignments C=2, D=2, B=4 is impossible in any perfect match, so those three 1s in the matrix can be zeroed, or those three edges in the graph can be deleted. Each of the remaining edges can appear in some perfect match, so that's the sum of the information derivable from that constraint at this point.

      Update: I should add that in some cases the number of possible values will be greater than the number of variables. In that case, a "perfect match" for the above argument would be a 2n-node cycle that covers each of the n variables: inevitably, some of the values would be left out in any one such match.

      Hugo

      Thinking about this further last night, I can refine the requirement to finding: that union of cyclic alternating paths which puts each node in the longest possible cycle. This page you referenced uses the discovery of alternating paths at the core of its algorithm - I need to analyse it further to see if it can be extended to discern the longest cycles.

      I was perhaps overly swayed by reading that the problem of "finding the longest cycle" is NP-hard - that is for a general graph, and it seems entirely possible that the special case of a bipartite graph introduces enough structure to make it rather easier.

      Hugo

Re: decomposing binary matrices
by johngg (Canon) on Feb 16, 2007 at 14:23 UTC
    This may be completely off target but the problem reminds me of the mental gymnastics used when solving Sudoku puzzles. I saw a Perl Sudoku solver once and the author had employed the Quantum::Superpositions module and it's any and all functions. Just a thought but perhaps something in there could help you.

    Cheers,

    JohnGG

      I bet Sudoku is behind this thread. I wrote a bruteforce solver last week, takes about 10 seconds for the "hard" ones on my three years old PC. I'll post it once I get to the office. I do have some more ideas, a wee bit less bruteforcish, though not at all similar to this.

      Update: Here is the blindly bruteforcish implementation. Needs about 11s to solve the "hard" sudokus on my Pentium 4. Making something like 400000 "what numbers are allowed on this place so far" tests.

      Update 2: Here is the promised improved version. It's quite similar except that there is an additional step. Whenever I make a guess I scan the whole plan for fields that are clear according to the fields already set and continue scanning and setting fields until there are no more clear ones and I have to find the next unset field in which I have to guess. This has brought the time from 11s down to 0.3s.

        From Limbic~Region's reply, it looks like you might have lost your bet. I too have a brute force solver that I wrote a couple of years ago. It would be interesting to compare our approaches so I'll dig my version out and post it as well. I actually wrote it before I had got into solving the puzzles by hand so I ought to have a go at refining it now that I have more strategies to hand.

        Cheers,

        JohnGG

        Update: Here is my brute-force Sudoku solver. Although it has to resort to backtracking if it makes a wrong guess it is fairly efficient because it sorts the empty squares by the number of possible numbers for each square before making a guess. Thus, for a lot of the time, it will make the right choice and it also updates everything and re-sorts after each choice. It will also detect an unsolveable puzzle very quickly as there will be a square with no possible number.

        It uses Term::ANSIColor to prettify the output but I'm not sure if that works in Windows terminals. Here's the code

        It reads the puzzle to be solved from a file specified on the command line and here's an example using the same puzzle grid as Jenda used.

        5...7.682 ...596... ......... ....8..49 .36...... ......... ..8..7..1 ..3..4..7 64.3...2.
        It seems to be a bit quicker than Jenda's solver but, as I've said, the guessing is somewhat optimised and it wasn't anything like as fast when first written.

        Cheers,

        JohnGG

        Jenda,
        I will take that bet. My guess is that it is for a number crossword solver. Of course, I already asked hv in the CB so what do I win?

        Cheers - L~R

Re: decomposing binary matrices
by pajout (Curate) on Feb 16, 2007 at 13:47 UTC
    Can you be more specific? I don't understand what is the goal and where is the issue... For instance, your two (split?) tables do not contain 1 for B4... For me it is possible to represent that structure as
    $possible_values = {A=>[2,4],B=>[3,4,5],...,E=>[2,4]};
    but it could mean nothing for your problem.
      pajout,
      B can't be 4. A or E must be 4. Which ever one is 4, the other must be 2 but B can never be 4.

      If I have understood the problem correctly, any time N variables can only be the same N values, they can be extracted from the matrix. This process is repeated until you are left with a "left over" matrix. Presumably this reduces the amount of brute force necessary to find values.

      This also sounds like a job best solved by Prolog or some other logic programming language as we are trying to searching to satisfy constraints.

      Cheers - L~R

        Thanks, I have not seen the 'each property have a distinct value' constraint... :>)
Re: decomposing binary matrices
by BrowserUk (Patriarch) on Feb 16, 2007 at 20:39 UTC

    At the risk of wasting your time a second time, I'm pretty sure that this method works. The method is based upon a half remembered technique for simplifying complex boolean conditions that I learnt at college and have never used since. You draw up a truth table for states and then swap whole columns or whole rows until the true values group together. I seem to recall that it didn't matter how many times you swapped things around so long as you always swapped whole columns or whole rows at a time

    My POC below basically consists of sorting the matrix both horizontally and vertically, and then picking out the sets with a equal number of 'leading zeros'. The problem I had was tracking the positions the 1's came from. The proper way would be to use a matrix of anonymous arrays (or objects), each containing the row, column and boolean value. For simplicity, I used arrays of strings, replacing each '1' by the letter of it's starting column, and appending the row numbers (starting at 1) to each string. I then sort these strings, then tranforms the 'matrix' into another set of strings and sort again. AT this point you extract and retain the 'row numbers' item from the array.

    What you end up with is the smallest group (least 1s/most 0s) sorted to the top. You count the number of leading zeros in group (min of the first two items) and select all the items with at least that number of leading zeros and place them into the first group. Then get the min leading zeros of the first two of the remaining items, and repeat. The final group will be the 'leftovers'.

    The following shows the process step by step for the OP example.

    c:\test>600418-2.pl This input 00CD01 A0CDE2 0B0D03 AB00E4 0BCD05 sorted 00CD01 0B0D03 0BCD05 A0CDE2 AB00E4 Tranformed looks like this 000AA 0BB0B C0CC0 DDDD0 000EE 13524 sorted 000AA 000EE 0BB0B 13524 C0CC0 DDDD0 These are the sets where the letters denote the columns of the origina +l matrix (0 mean column not used in this set). And the numbers above, the rows they came from. 13524 ## Column numbers from the original data. Trim leading zeros. 000AA ## Read this as; Group one contains 000EE ## columns A & E from rows 2 & 4. 13524 ## Leftovers group. Trim trailing columns used by earlier group +s. 0BB0B ## Columns B, C, & D from Rows 1, 3 & 5. C0CC0 DDDD0

    This works as is for the other examples you've supplied (see commented out data blocks).

    I do remember from those far off college days that for some complex examples, it was possible for the grouping to 'wrap over the edges'. That is, if you draw the matrix on paper, and wrap it into a cylinder to bring the left and right edges together, a group could cross the boundary. The same was possible for the top & bottom edges.

    I think that this would be catered for by repeating the sort/transform/sort and select process on the smaller groups, but I haven't taken it that far yet. Unless your matrices are huge, repeating the process to subdivide the smaller groups shouldn't be a problem.

    #! perl -slw use strict; sub xform { my @out; for my $in ( @_ ) { $out[ $_ ] .= substr $in, $_, 1 for 0 .. length( $in ) -1; } return @out; } my @grid = ( "00CD01", "A0CDE2", "0B0D03", "AB00E4", "0BCD05", ); #my @grid=( "000DEF1", "000DEF2", "000DE03", "ABCDEF4", "ABCDEF5", "AB +0DEF6", ); #my @grid=( "000DE01", "000D0F2", "0000EF3", "AB00004", "A0C0005", "AB +00006", ); #my @grid=( "0B0D001", "000DE02", "0B00E03", "A0000F4", "A0C0005", "A0 +000F6", ); print "This input\n"; print "\t$_" for @grid; @grid = sort @grid; print "sorted\n"; print "\t$_" for @grid; my @xformed = xform @grid; print "\nTranformed looks like this\n"; print "\t$_" for @xformed; @xformed = sort @xformed; print "sorted\n"; print "\t$_" for @xformed; ## extra column label item. my( $label ) = grep /1/, @xformed; @xformed = grep !/1/, @xformed; my @subsets; while( @xformed ) { my $mask = $xformed[ 0 ] | $xformed[ 1 ]; if( $mask =~ m[(^0+)] ) { my $count = length( $1 ); ## Length of common zero prefix push @{ $subsets[ @subsets ] }, shift( @xformed ), shift( @xfo +rmed ); while( @xformed and $xformed[ 0 ] =~ m[(^0+)] and length( $1 ) == $count ) { push @{ $subsets[ -1 ] }, shift @xformed; } } else { push @subsets, []; push @{ $subsets[ -1 ] }, shift @xformed while @xformed; } } print <<'EOS'; These are the sets where the letters denote the columns of the origina +l matrix (0 mean column not used in this set). And the numbers above, the rows they came from. EOS print join "\n", $label, @$_, "\n" for @subsets;

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.

      I think that approach has possibilities, though it might need some modification - there is no guarantee that the row with fewest bits is separable. Consider, say:

      A: 1 1 0 0 0 B: 1 0 1 1 0 C: 1 0 1 1 0 D: 1 0 1 1 0 E: 1 1 1 1 1
      .. from which {B, C, D} is a separable submatrix. I'd have to think further whether I can easily construct an example that defeats the approach on both rows and columns simultaneously - it'd certainly need a larger matrix (at least 7x7 I think), but I think the same general idea could throw up a proper counterexample.

      At the risk of wasting your time ...

      Not a waste by any means - many of the suggestions so far could maybe be adaptable to a full solution. It's just a question of whether the adapted version would end up any quicker than going brute force in the first place. :)

      Hugo

        I just ran that example through the code I posted (Note: My code uses letters for columns not rows as you have). The groupings produced:

        23415 0000E 000BB 23415 AAAAA CCC0C DDD0D

        gives rows 1 & 5 (your A & E), as a group which when subtracted from the remainer leaves rows 2, 3 & 4 (your {BCD}) as a group which is what you are after?

        Full output from the unchanged program (except for inserting the new data (first line below)):

        # my @grid = ( "AB0001","A0CD02","A0CD03","A0CD04","ABCDE5" ); c:\test>600418-2.pl This input AB0001 A0CD02 A0CD03 A0CD04 ABCDE5 sorted A0CD02 A0CD03 A0CD04 AB0001 ABCDE5 Tranformed looks like this AAAAA 000BB CCC0C DDD0D 0000E 23415 sorted 0000E 000BB 23415 AAAAA CCC0C DDD0D These are the sets where the letters denote the columns of the origina +l matrix (0 mean column not used in this set). And the numbers above, the rows they came from. 23415 0000E 000BB 23415 AAAAA CCC0C DDD0D

        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
Re: decomposing binary matrices
by moklevat (Priest) on Feb 16, 2007 at 15:59 UTC
    I was initially going to suggest principal components analysis as a solution, since the example decomposition you presented appears to be a clustering problem. I would then have pointed you to PDL and PDL::PCA. However, after reading some of the other comments my poor old neuron suspects that there is something more afoot that may invalidate PCA for the general case.

      I'm afraid I can't understand very much of the description of principal components analysis; as far as I can tell though, it requires an interpretation of what the source data represents quite unconnected with what my data represents. The fact that no mention is made of the special case of binary matrices reinforces that view in my mind.

      Hugo

Re: decomposing binary matrices
by fenLisesi (Priest) on Feb 16, 2007 at 14:13 UTC
    Represent columns as bitmaps and use the bitmaps as hash keys?

    Update: I am sorry -- I see that Limbic~Region just suggested this in the CB, probably before I posted this.

      fenLisesi,
      I didn't post yet because I wanted to make sure hv agreed that it could work (he hasn't yet). The algorithm may not be the most efficient but it should be something like 2N where N represents the number of columns

      Treat each column as a bitstring. Walk each column and push the column index into a hash key (the bitstring itself). At the end, walk the hash looking for hash keys with a value count that is the same as the number of bits in the key. Since the value is an array of the column indices, you know what columns to extract.

      Cheers - L~R

        Sticking with the bitstring concept, I think rather that you are looking for a subset of n bitstrings such that the bitwise-OR of the bitstrings has only n distinct bits set.

        Note that some or all of those bitstrings may have fewer than n bits set; you may even have two bitstrings that have no bit set in common in a qualifying subset (though you'd need a minimum of 4 elements in the subset to avoid it being further decomposable).

        Hugo

        I was thinking of storing the string 'A' as the value for the key which consists of, for this example, the byte that has bits '01010000' (the last three zeros padding).

      I don't think that is sufficient: a submatrix need not have all ones, as for example in the 3x3 submatrix of the example. Indeed, a 3x3 submatrix could have bit-patterns 110, 101, 011 such that no two rows or column are the same, nor is any row or column all ones.

      Hugo

Re: decomposing binary matrices
by superfrink (Curate) on Feb 16, 2007 at 21:28 UTC
    I think you are looking to simplify a "Karnaugh map". You might also look for code that simplify boolean expressions not represented as a k-map like the "Quine–McCluskey algorithm".

    Update: I think I'm out to lunch. The axis of the matrix in your post do not look like they represent a boolean expression. My comment probably doesn't apply to your problem. :( I think it might be coffee time for me.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://600418]
Approved by Joost
Front-paged by grinder
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others perusing the Monastery: (5)
As of 2024-03-28 14:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found