title: Implement inclusion-exclusion efficiently
body: <p>An am trying to implement <a href="https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle" rel="nofollow noreferrer">inclusion-exclusion</a> efficiently for the following values:</p>
  
  <pre><code>2/5, 2/5, 2/10, 2/10, 2/15, 2/15, ...
  </code></pre>
  
  <p>Of course, the program cannot run infinitely long, so I'd like to put a configurable limit on the number of terms.</p>
  
  <p>For example, let's say I limit my calculation to:</p>
  
  <pre><code>2/5, 2/5, 2/10, 2/10
  </code></pre>
  
  <p>Then the calculation would be:</p>
  
  <pre><code>+ 2/5 + 2/5 + 2/10 + 2/10                  # choose 1 out of 4 terms
  - 4/25 - 4/50 - 4/50 - 4/50 - 4/50 - 4/100 # choose 2 out of 4 terms
  + 8/250 + 8/250 + 8/500 + 8/500            # choose 3 out of 4 terms
  - 16/2500                                  # choose 4 out of 4 terms
  </code></pre>
  
  <p>I find doing "choose x out of y" in an iterative manner to be a bit complicated.</p>
  
  <p>Here is my current implementation:</p>
  
  <pre><code>from decimal import Decimal
  from decimal import getcontext
  
  getcontext().prec = 100
  
  def getBits(num):
      bit = 0
      bits = []
      while num &gt; 0:
          if num &amp; 1:
              bits.append(bit)
          bit += 1
          num &gt;&gt;= 1
      return bits
  
  def prod(arr):
      res = Decimal(1)
      for val in arr:
          res *= val
      return res
  
  SIZE = 20
  sums = [Decimal(0) for k in range(SIZE)]
  temp = [Decimal(2)/(5*k) for k in range(1,SIZE)]
  probabilities = [p for pair in zip(temp,temp) for p in pair][:SIZE]
  
  for n in range(1,1&lt;&lt;SIZE):
      bits = getBits(n)
      sums[len(bits)-1] += prod([probabilities[bit] for bit in bits])
  
  total = 0
  for k in range(SIZE):
      total += sums[k]*(-1)**k
  print(total)
  </code></pre>
  
  <p>As you can see, I do the "choose x out of y terms" by generating every possible bit-combination between <code>1</code> and <code>2 ** SIZE</code>, and then choosing the terms in the <code>probabilities</code> array which are located in the positions which are marked <code>1</code> in the current bit-combination.</p>
  
  <p>I am essentially looking for a more efficient way to do this, as the number of iterations grows exponentially by the value of <code>SIZE</code>.</p>
  
  <p>I am aware of the fact that it might not be feasible, because the total number of terms in the inclusion-exclusion expression is technically exponential (the sum of a row in Pascal triangle).</p>
  
  <p>However, since the values in <code>probabilities</code> are all known and "nice" (i.e., a power of 2 divided by a product of 5), I've figured that there is possibly a "shortcut" here which I have overlooked.</p>