Я пытаюсь эффективно реализовать включение-исключение для следующих значений:
2/5, 2/5, 2/10, 2/10, 2/15, 2/15, ...
Конечно, программа не может работать бесконечно долго, поэтому я хотел бы поставитьнастраиваемый лимит на количество терминов.
Например, допустим, я ограничил свой расчет:
2/5, 2/5, 2/10, 2/10
Тогда расчет будет:
+ 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
Iнайти, что «выбрать x из y» итеративным способом немного сложнее.
Вот моя текущая реализация:
from decimal import Decimal
from decimal import getcontext
getcontext().prec = 100
def getBits(num):
bit = 0
bits = []
while num > 0:
if num & 1:
bits.append(bit)
bit += 1
num >>= 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<<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)
Как вы можете видеть, я делаю «выбор»x из y термов "путем генерации каждой возможной битовой комбинации между 1 и 2 ** SIZE, а затем выбора термов в массиве probabilities, которые расположены в позициях, отмеченных 1 в текущем битовом коде.комбинация.
Я, по сути, ищу более эффективный способ сделать это, поскольку число итераций растет экспоненциально на величину SIZE.
Я осознаю тот факт, что этоможет быть неосуществимым, потому чтообщее количество членов в выражении включения-исключения является технически экспоненциальным (сумма строки в треугольнике Паскаля).
Однако, поскольку значения в probabilities все известны и «хороши» (т. е.степень 2, деленная на произведение 5), я подумал, что здесь, возможно, есть «ярлык», который я упустил.
Большое спасибо за любые идеи !!!