http://qs1969.pair.com?node_id=600449

in reply to decomposing binary matrices

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 ];
}
}