Как перебрать декартово произведение десяти списков (по десять элементов в каждом) быстрее? (Вероятность и кости)

Question

Я пытаюсь решить эту задачу . Для этой цели я написал function, который использует itertools.product () для декартового произведения итераций ввода:

def probability(dice_number, sides, target):
    from itertools import product
    from decimal import Decimal
    FOUR_PLACES = Decimal('0.0001')
    total_number_of_experiment_outcomes = sides ** dice_number
    target_hits = 0
    sides_combinations = product(range(1, sides+1), repeat=dice_number)
    for side_combination in sides_combinations:
        if sum(side_combination) == target:
            target_hits += 1
    p = Decimal(str(target_hits / total_number_of_experiment_outcomes)).quantize(FOUR_PLACES)
    return float(p)

При вызове probability(2, 6, 3) вывод равен 0.0556, поэтому работает нормально. Но вызов probability(10, 10, 50) вычисляет veeery long (часы?), Но должен быть лучший способ:)
for side_combination in sides_combinations: занимает много времени, чтобы перебрать огромное количество sides_combinations.

Пожалуйста, можете Вы помогаете мне узнать, как ускорить расчет результата, я тоже хочу спать сегодня вечером.

Answer 1

Если кто-то все еще интересуется решением, которое позволяет избежать очень-очень-очень длинных итераций во всех продуктах itertools.product, то это:

def probability(dice_number, sides, target):
    if dice_number == 1:
        return (1 <= target <= sides**dice_number) / sides
    return sum([probability(dice_number-1, sides, target-x) \
                        for x in range(1,sides+1)]) / sides

Но вы должны добавить кеширование функции probability результаты, если нет - вычисление вероятности займет очень-очень-очень много времени)

PS этот код на 100% не мой, я взял его из inte rnet, я ' Я не такой умный, чтобы придумывать это сам, надеюсь, вам понравится так же, как и мне.

Answer 2

Полагаю, проблема в том, чтобы найти распределение суммы костей. Эффективный способ сделать это с помощью дискретной свертки. Распределением суммы переменных является свертка их вероятностных массовых функций (или плотностей в непрерывном случае). Convolution - это n-арный оператор, так что вы можете удобно вычислять его только по двум pmf за раз (текущее распределение итогов и следующий в списке). Затем из окончательного результата вы можете считать вероятности для каждой возможной суммы. Первый элемент в результате - это вероятность наименьшего возможного итога, а последний элемент - это вероятность наименьшего возможного итога. В промежутке между ними вы можете выяснить, какая из них соответствует конкретной сумме, которую вы ищете.

Трудная часть этого процесса - свертка, поэтому сначала поработайте над этим. Это просто простое суммирование, но немного сложно получить правильные пределы суммирования. Мой совет - работать с целыми или рациональными числами, чтобы вы могли точно вычислить арифметику c.

. После этого вам просто нужно построить соответствующий pmf для каждого ввода d ie. Входные данные просто [1, 1, 1, ... 1], если вы используете целые числа (в конечном итоге вам придется нормализовать) или [1 / n, 1 / n, 1 / n, ..., 1 / n] если рационально, где n = количество граней. Кроме того, вам нужно правильно обозначить индексы выходных данных - опять же, это немного сложно сделать правильно.

Свертка - это очень общий подход для суммирования переменных. Это может быть сделано еще более эффективным путем реализации свертки посредством быстрого преобразования Фурье, поскольку FFT (conv (A, B)) = FFT (A) FFT (B). Но на данный момент я не думаю, что вам нужно беспокоиться об этом.