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


in reply to Re: decomposing binary matrices
in thread 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