Re^2: 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
[download]

.. 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

Comment on Re^2: decomposing binary matrices Download Code

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` [download] 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` [download] 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. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply] [d/l] [select]
Re^4: decomposing binary matrices by hv (Parson) on Feb 17, 2007 at 13:11 UTC
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");` [download] Hugo	[reply] [d/l]


more useful options
	PerlMonks