Re^2: decomposing binary matrices

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

Comment on Re^2: decomposing binary matrices

Replies are listed 'Best First'.
Re^3: decomposing binary matrices by hv (Prior) on Feb 16, 2007 at 14:25 UTC
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	[reply]
Re^4: decomposing binary matrices by Limbic~Region (Chancellor) on Feb 16, 2007 at 14:28 UTC
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	[reply]
Re^3: decomposing binary matrices by fenLisesi (Priest) on Feb 16, 2007 at 14:26 UTC
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).	[reply]