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

in reply to decomposing binary matrices

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.

Replies are listed 'Best First'.
Re^2: decomposing binary matrices
by Limbic~Region (Chancellor) on Feb 16, 2007 at 14:20 UTC
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

hv,
I understand now that to be considered for extraction, a variable need not have the exact same 1s and 0s in common. I need to go but I still think this sounds like a good logic programming candidate.

Cheers - L~R

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).
Re^2: decomposing binary matrices
by hv (Parson) on Feb 16, 2007 at 14:16 UTC

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