# find all subsets sutisfying given participation constraints

• Sep 25th 2010, 06:00 AM
ktotam
find all subsets sutisfying given participation constraints
Hello,

Given:
a) N finite sets A1 through AN
b) Cartezian product R formed from these sets.
c) Constraint participation vectors:
maxC=(max_c1,max_c2,...,max_cN)
minC=(min_c1,min_c2,...,min_cN)

How to find all subsets S of R which sutisfy constraint maxC and minC?

The interpretation of constraints minC and maxC is:
the member from set A1 appears at least min_c1 and at most maxc1 times in subset S
the member from set A2 appears at least min_c2 and at most maxc2 times in subset S
...
the member from set AN appears at least min_cN and at most maxcN times in subset S

First i tried to solve the special case minC=maxC.
I figured out that i need to calculate least common multiplier for constraint verctor that gives me the size of sets S.
then i could reduce the problem a little bit by calculating the number of members from each set Ai that must be selected to construct set S. so from original cartezian product R i could get a smaller cartezian product.
then i tried to use inclusion-exclusion principle but can't not continue with solution... the calculation of size of intersections is seems to be complicated..

an example:
A={a b} B={! ? \$} C={P Q R}
minC=maxC=(2,1,1)

the number of sets S that sutisfy the constraint is 36

Would appreciate a help with this problem.

Thanks