Pathologically Eclectic Rubbish Lister PerlMonks

### Re^2: decomposing binary matrices

by hv (Parson)
 on Feb 16, 2007 at 22:56 UTC ( #600539=note: print w/replies, xml ) Need Help??

in reply to Re: decomposing binary matrices

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

Replies are listed 'Best First'.
Re^3: decomposing binary matrices
by BrowserUk (Pope) on Feb 16, 2007 at 23:11 UTC

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.

Sorry, I transformed the data already, and included more than necessary. Try this instead (in which, again, {B, C, D} yield a separable submatrix):

```  my @grid = ( "ABCD1", "A0002", "0BCD3", "0BCD4");

Hugo

Create A New User
Node Status?
node history
Node Type: note [id://600539]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (5)
As of 2017-10-21 03:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My fridge is mostly full of:

Results (269 votes). Check out past polls.

Notices?