počet testů [odporná hrubá síla]

#!/bin/env python3.8

import fractions

def subsets(n, k):
  if k == 0:
    yield ()
  elif k < n:
    for s in subsets(n - 1, k):
      yield s
    for s in subsets(n - 1, k - 1):
      yield s + (n - 1,)
  elif n == k:
    yield tuple(range(n))

class NumberOfTests:
  def __init__(self, depth):
    self.patients = 2 ** depth

  def report(self, tested, sample):
    sample += self.patients
    while sample > 1:
      if sample in tested:
        break
      tested.add(sample)  # current vertex
      tested.add(sample + (-1 if sample % 2 else 1))  # sibling
      sample //= 2  # path to the root

  def averageTests(self, infected):
    infected_subsets = 0
    all_tests_done = 0
    for subset in subsets(self.patients, infected):
      tested = {1}
      infected_subsets += 1
      for sample in subset:
        self.report(tested, sample)
      all_tests_done += len(tested)
    return fractions.Fraction(all_tests_done, infected_subsets)

DEPTH = 6
MAX_INFECTED = 5  # too slow for more
MIN_INFECTED = 59  # too slow for less

nt = NumberOfTests(DEPTH)
for r in (range(MAX_INFECTED + 1), range(MIN_INFECTED, 2 ** DEPTH + 1)):
  for i in r:
    blah = nt.averageTests(i)
    print(f'{i:02}: {float(blah)} ({str(blah)})')