fast_product.py

import time
from collections import Counter
from pprint import pprint


def all_sums(values, threshold, previous_sums=None):
    """
    values must be sorted
    previous_sums is a Counter of previously obtained possible sums

    Returns a Counter of all possible sums of values and the previous sums
    """
    if not previous_sums:
        previous_sums = Counter({0: 1})

    new = Counter()
    for existing_sum, ex_sum_count in sorted(previous_sums.items()):
        for index, val in enumerate(values):
            total = existing_sum + val
            if total < threshold:
                # With the current value, we have found ex_sum_count
                # ways to obtain that total
                new.update({total: ex_sum_count})
            else:
                # We don't need the exact sum, as anything we could
                # later add to it will be over the threshold.
                # We count them under the value = threshold
                # As 'values' is sorted, all subsequent values will also give
                # a sum over the threshold
                values_left = len(values) - index
                new.update({threshold: values_left * ex_sum_count})
                break
    return new


def count_sums(values, threshold, repeat):
    """
    values must be sorted!

    Recursively calculates the possible sums of 'repeat' values,
    counting together all values over 'threshold'
    """
    if repeat == 1:
        return all_sums(values, threshold, previous_sums=None)
    else:
        return all_sums(values, threshold, previous_sums=count_sums(values, threshold, repeat=repeat - 1))


if __name__ == '__main__':
    start_time = time.time()
    confs = range(10, 11)

    for i in confs:
        loops = i
        results = [4, 2.75, 2.75, 2.75, 2.75, 1.5, 1.5, 1.5, 1.5, 1.5, 1.5, 0.25, 0.25, 0.25, 0.25, 0]
        threshold = loops * 2
        values = sorted(results)
        sums = count_sums(values, threshold, repeat=loops)
        number_of_sums = len(results) ** loops
        good = sums[threshold]
        bad = number_of_sums - good
        print("Questions: {0}, Result: {1:.6f}%, time elapsed: {2:.2f}s".format(i, 100 * good / (good + bad),
                                                                                time.time() - start_time))
        pprint(sums)