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 ]; } }
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.
In Section
Seekers of Perl Wisdom