Member Avatar for pranay_agg

hi , i am having difficulty in implementing the basic mathematic principle of inclusion-exclusion. I want to find the no. of numbers in a range from 1 to N which are divisible by another set of numbers where size of set <= 15.
Now the problem i am facing is that how do i consider the loops for calculating pair wise, three -wise , four - wise etc, because if the size is 2 i need to calculate a1+a2-a1*a2. ,where a1 is the no. of elements in set i to N divisible by 1st no of the second set , and so on, thus 1 loop
for n=3
a1+a2+a3-(a1*a2) -(a1*a3)-(a2*a3)-(a1*a2*a3) so 2 loops .
similarly for 4 , there should be 4 loops and so on thus rending the programme very lenghty and inefficient , so how should i implement it?

  • 2 Contributors
  • 1 Reply
  • 546 Views
  • 3 Weeks Discussion Span
  • Latest Post Latest Post by schaub1st
Member Avatar for schaub1st

Hi Pranay_agg,

Don't know if this is still relevant, hope this helps.

You should notice that for every [TEX]$a_i$[/TEX] you add, the sums of products of k elements is always the sum of products of k elements without that a_i plus the sum of products of k-1 elements without [TEX]a_i[/TEX] times [TEX]a_i[/TEX].

e.g. a1+a2+a3-(a1*a2) -(a1*a3)-(a2*a3)+(a1*a2*a3) ==
(a1 + a2) + 1*a3 +(-1)[(a1*a2)+ (a1+a2)*a3] + [a1*a2*a3+0]

Using this fact, you can keep an array of length n+1 (where n is the number of elements you want to check for) with the first value being 1. For each element a_i you want to add, fill in the sum of products of j elements (with j going from i+1 to 1 with the i+1-th sum initialized to 0) in the following fashion: the sum of products of j elements = (previous) sum of j elements + (previous)sum of j-1 elements * a_i.

Finally, sum the elements of the array times 1 or -1, as the case may be, according to the inclusion-exclusion principle (notice you had a slight mistake, putting the coefficient of a1*a2*a3 as -1. instead of 1).

I'd post code, but I think that from this point on it should be pretty easy to implement (let me know if i'm wrong in thinking so). Notice that this method doesn't take care of the general inclusion-exclusion principle where [TEX]$|A_i\cap A_j|\neq |A_i|*|A_j|$[/TEX], but it should serve you well for the problem at hand.

Enjoy,
Schaub1st

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.