Prev: Error message in setting up Matlab_R2008a
Next: word occurence counting (DNA)
From: Walter Roberson on 31 Mar 2010 17:03
red wrote:
> My problem is: See if each subset of the set {1,...,n} fulfills some
> condition. For each subset, say A, I have to compare A with all other
> subsets of {1,...,n}. Since there are 2^n subsets, as n grows, it is not
> feasible to store all the subsets.


Do you really have to compare with all other subsets? Often there is some kind
of pruning that can be undertaken; e.g., if A vs B fails the test, then A vs
(B union C) may also be known to fail the test, making it potentially
unnecessary to generate anything that includes B as a subset.

If, for each generated subset, you just need to know that presence or absence
of particular members, then map the problem into an unsigned n-bit integer (or
array of such integers). For example with n = 30, you could used uint32 and
then use bit-level tests to see if any particular member was present or not.
bitand() is one of the few operations supported on uint64, but not much else
is, so it can often be easier to work with uint32. To generate the next subset
from a uint32 number, just add 1 to the number if you are taking the naive
approach. If you are using an array of uint32 numbers, then if the result
after incrementing is 0, then increment the next array along ("carry the
1")... and make the 0 check on that result too. You are done your list when
your carry would "fall off the end of the array".


With the bitmapped approach, the powerset would simply be the list of all
numbers from 0 to 2^n - 1 -- and there is no point in storing that. There
would, however, be a point in storing the subset pairs that "pass" what-ever
test you are doing, and that is something you haven't taken into account in
your description -- unless you have a good estimate of the number of pairs, or
a known upper-bound, then you are likely going to end up growing your holding
array, and that will be an expensive operation that could chew through your
memory.
 | 
Pages: 1
Prev: Error message in setting up Matlab_R2008a
Next: word occurence counting (DNA)