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