Как рассчитать вероятность получения суммы X с использованием N шестигранных кубиков

Question

Задача: Например, какова вероятность получения суммы 15 при использовании 3 шестигранных кубика. Это может быть, например, получение 5-5-5 или 6-6-3 или 3-6-6 или многих других вариантов.

Решение для грубой силы на 2 кубика - со сложностью 6 ^ 2:

Предполагая, что у нас было только 2 шестигранных кубика, мы можем написать очень простой c код, подобный этому:

public static void main(String[] args) {
   System.out.println(whatAreTheOdds(7));
}

public static double whatAreTheOdds(int wantedSum){
    if (wantedSum < 2 || wantedSum > 12){
        return 0;
    }

    int wantedFound = 0;
    int totalOptions = 36;

    for (int i = 1; i <= 6; i++) {
        for (int j = 1; j <= 6; j++) {
            int sum = i+j;
            if (sum == wantedSum){
                System.out.println("match: " + i  + " " + j );
                wantedFound +=1;
            }
        }
    }

    System.out.println("combinations count:" + wantedFound);
    return (double)wantedFound / totalOptions;
}

И вывод для 7 будет:

совпадение: 1 6

совпадение: 2 5

совпадение: 3 4

совпадение: 4 3

совпадение: 5 2

совпадение: 6 1

количество комбинаций: 6

0.16666666666666666

Вопрос в том, как Чтобы обобщить алгоритм для поддержки N костей:

public static double whatAreTheOdds(int wantedSum, int numberOfDices)

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

Я думал что-то вроде этого:

 public static double whatAreTheOdds(int sum, int numberOfDices){

    int sum;
    for (int i = 0; i < numberOfDices; i++) {
        for (int j = 1; j <= 6; j++) {

        }
    }
}

, но не удалось найти правильный алгоритм.

Еще одна проблема здесь - есть ли способ сделать это эффективно, а не в сложности 6 ^ N?

Answer 1

Поскольку ответ Алекса отмечает, есть комбинаторная формула для этого:

В этой формуле p является сумма выпавших чисел (X в вашем вопросе), n - количество кубиков, а s - количество сторон каждой кости (6 в вашем вопросе). Независимо от того, оцениваются ли биномиальные коэффициенты с использованием циклов или предварительно вычисляются с использованием треугольника Pascal, в любом случае сложность времени равна O (n ² ), если мы возьмем s = 6 в качестве константы и X - n быть O (n).

---

Вот альтернативный алгоритм, который вычисляет все вероятности одновременно. Идея состоит в том, чтобы использовать дискретную свертку для вычисления распределения суммы двух случайных величин с учетом их распределений. Используя подход «разделяй и властвуй», как в возведении в степень при возведении в квадрат алгоритма , нам нужно только выполнить O (log n) сверток.

Псевдокод находится ниже; sum_distribution(v, n) возвращает массив, где значение в индексе X - n является числом комбинаций, в которых сумма n бросков костей равна X.

// for exact results using integers, let v = [1, 1, 1, 1, 1, 1]
// and divide the result through by 6^n afterwards
let v = [1/6.0, 1/6.0, 1/6.0, 1/6.0, 1/6.0, 1/6.0]

sum_distribution(distribution, n)
    if n == 0
        return [1]
    else if n == 1
        return v
    else
        let r = convolve(distribution, distribution)
        // the division here rounds down
        let d = sum_distribution(r, n / 2)
        if n is even
            return d
        else
            return convolve(d, v)

Свертка не может быть выполнена за линейное время, поэтому во время выполнения преобладает последняя свертка на двух массивах длиной 3n, поскольку другие свертки находятся на достаточно более коротких массивах.

Это означает, что если вы используете простой алгоритм свертки, он должен принимать O (n ² ) время для вычисления всех вероятностей, и если вы используете быстрое преобразование Фурье , тогда это займет O (n log n) времени.

Answer 2

Вот рекурсивное решение с запоминанием для подсчета комбинаций.

import java.util.Arrays;
import java.lang.Math;

class Dices {
    public static final int DICE_FACES = 6;

    public static void main(String[] args) {
        System.out.println(whatAreTheOdds(40, 10));
    }

    public static double whatAreTheOdds(int sum, int dices) {
        if (dices < 1 || sum < dices || sum > DICE_FACES * dices) return 0;

        long[][] mem = new long[dices][sum];
        for (long[] mi : mem) {
            Arrays.fill(mi, 0L);
        }
        long n = whatAreTheOddsRec(sum, dices, mem);
        return n / Math.pow(DICE_FACES, dices);
    }

    private static long whatAreTheOddsRec(int sum, int dices, long[][] mem) {
        if (dices <= 1) {
            return 1;
        }
        long n = 0;
        int dicesRem = dices - 1;
        int minFace = Math.max(sum - DICE_FACES * dicesRem, 1);
        int maxFace = Math.min(sum - dicesRem, DICE_FACES);
        for (int i = minFace; i <= maxFace; i++) {
            int sumRem = sum - i;
            long ni = mem[dicesRem][sumRem];
            if (ni <= 0) {
                ni = whatAreTheOddsRec(sumRem, dicesRem, mem);
                mem[dicesRem][sumRem] = ni;
            }
            n += ni;
        }
        return n;
    }
}

Вывод:

0.048464367913724195

РЕДАКТИРОВАТЬ: Для записи сложность этого алгоритма по-прежнему O ( 6 ^ n), этот ответ просто нацелен на то, чтобы дать возможную реализацию для общего случая, которая лучше, чем простейшая реализация, используя запоминание и сокращение пространства поиска (исследуя только возможные решения).

Answer 3

Возможно, вы захотите взглянуть на статью Вольфрама для совершенно другого подхода, который вычисляет желаемую вероятность с помощью одного l oop.

Answer 4

Идея состоит в том, чтобы иметь массив, хранящий текущее «состояние» каждой кости, начиная с каждой кости по одному и считая вверх. Например, с тремя кубиками вы сгенерируете комбинации:

111
112
...
116
121
122
...
126
...
665
666

Когда у вас есть состояние, вы можете легко найти, является ли сумма той, которую вы ищете.

Я ухожу детали для вас, как кажется, полезное упражнение обучения:)