Как посчитать распределение кубиков в специфической ситуации
что такое "k больших кубов"?
http://anydice.com/program/887 - вот пример.
Это значит вы делаем выбрку (0 < k < l) из сортированного списка выпавших значений кубов, отбирая k максимальных значений.
Это значит вы делаем выбрку (0 < k < l) из сортированного списка выпавших значений кубов, отбирая k максимальных значений.
Если всё подряд мемоизировать, разве не получится полиномиально?
Я вижу как сделать полиномиально от k**m (k в степени m но это грустно.
Попробуй метод Монте Карло, вещь
А сколько попыток надо сделать, чтобы получить заданную точность для слегка смещённого почти нормального распределения?
Пока у меня вышло l^2 + m^2k^2(m+l-k) без учёта стоимости длинной арифметики. Идея придумать какую-то свёртку и применять её на ходу благополучно провалилась, но получилось сделать декомпозицию, разбив все возможные случаи на классы, которые относительно легко можно посчитать.
Рассмотрим все возможные варианты уже отсортированного списка. Каждый вариант можно представить как [lesser] + [same] + [effective]; где same - ненулевой список из одного и того же элемента, примечательного тем, что это минимальный, входящий в выборку элемент, lesser - элементы, строго меньшие минимально входящего, а значит нам не интересные, нужно только сосчитать их суммарную вероятность, effective - значимые элементы списка, которые будут суммироваться. В вырожденном случае все списки пусты, кроме same. effective - это по факту нарастающие суммы дайсов, которые считаются как будто они единственные, и никакого выбора большего элемента нет, и можно на каждом шагу полностью сворачивать вероятности выпадания разных значений. Каждый сортированный вариант может быть получен из нескольких разных несортированных, так что он ещё домножается на соответствующие комбинации.
Общая сложность выходит вот каким образом:
1. l^2: Предварительное вычисление C(n,k) для n <= l
2. m : мы перебираем отдельно все возможные значения для same - их столько же, сколько сторон куба
3. k*(l-k) : для каждого same мы рассматриваем возможные сочетания длин lesser и effective
4. m*k : применение effective для каждого сочетания из третьего пункта требует полного прохода по пространству свёртки
5. m^3k^2: вычисление свёртки при увеличении длины effective выполняется для каждого same и effective и зависит от размера самой свёртки
В инклюдах - тривиальная самописная табличка для предвычислений C(n,k) и внешняя библиотека spire, потому что встроенные библиотеки scala обделены поддержкой длинной арифметики.
Очевидно как расширить эту методику на произвольные распределения вероятностей, на выборку из окна, обрезанного с двух сторон, а не только снизу, как здесь, и любой монотонный метод сворачивания, а не только сумму.
Меня беспокоит получившая пятая степень. Как-то слишком быстро деградирует производительность с ростом задачи. Можно можно как-то по другому произвести декомпозицию получившихся вариантов, чтобы не приходилось так много циклов нарезать внутри?
Пока у меня вышло l^2 + m^2k^2(m+l-k) без учёта стоимости длинной арифметики. Идея придумать какую-то свёртку и применять её на ходу благополучно провалилась, но получилось сделать декомпозицию, разбив все возможные случаи на классы, которые относительно легко можно посчитать.
Рассмотрим все возможные варианты уже отсортированного списка. Каждый вариант можно представить как [lesser] + [same] + [effective]; где same - ненулевой список из одного и того же элемента, примечательного тем, что это минимальный, входящий в выборку элемент, lesser - элементы, строго меньшие минимально входящего, а значит нам не интересные, нужно только сосчитать их суммарную вероятность, effective - значимые элементы списка, которые будут суммироваться. В вырожденном случае все списки пусты, кроме same. effective - это по факту нарастающие суммы дайсов, которые считаются как будто они единственные, и никакого выбора большего элемента нет, и можно на каждом шагу полностью сворачивать вероятности выпадания разных значений. Каждый сортированный вариант может быть получен из нескольких разных несортированных, так что он ещё домножается на соответствующие комбинации.
Общая сложность выходит вот каким образом:
1. l^2: Предварительное вычисление C(n,k) для n <= l
2. m : мы перебираем отдельно все возможные значения для same - их столько же, сколько сторон куба
3. k*(l-k) : для каждого same мы рассматриваем возможные сочетания длин lesser и effective
4. m*k : применение effective для каждого сочетания из третьего пункта требует полного прохода по пространству свёртки
5. m^3k^2: вычисление свёртки при увеличении длины effective выполняется для каждого same и effective и зависит от размера самой свёртки
package object Largest {
import spire.implicits._
import spire.math._
import spire.math.Sorting.quickSort
import TableFunc.TCombiFull
val C = TCombiFull
private def convolution(dice : Int, original : Array[BigInt]) : Array[BigInt] = {
val len = original.length + dice - 1
val out : Array[BigInt] = new Array(len)
var b = 0
var e = len - 1
var sum = BigInt(0)
while (b < dice) {
sum += original(b)
out(b) = sum
out(e) = sum
b += 1
e -= 1
}
var d = 0
while(b <= e) {
sum += original(b)
sum -= original(d)
out(b) = sum
out(e) = sum
b += 1
d += 1
e -= 1
}
out
}
private def lesser_or_equal(total : Int, significant : Int, dice : Int) : BigInt = {
var sum = BigInt(0)
var lesser = BigInt(dice - 1)
for (i <- 1 to total - significant) {
sum += lesser * C(total, i) // C(n,l) ≡ C(n,n-l)
lesser *= (dice-1)
}
sum + 1
}
override def apply(length : Int, largest : Int, dice : Int) : Array[Rational] = {
require(dice > 1)
require(largest > 0)
require(length >= largest)
val outInterval = dice * largest + 1
val output : Array[BigInt] = Array.fill(outIntervalBigInt(0
output(largest) = BigInt(1)
for (d <- 2 to dice)
output(largest * d) = lesser_or_equal(length,largest,d)
val dice_sum : Array[Array[BigInt]] = new Array(dice-1)
for (d <- 1 until dice)
dice_sum(d-1) = Array.fill(dBigInt(1
for (step <- 1 until largest) {
val residual = length - step
val prefix = largest - step
val select_greater = C(length,step)
var dp = dice - 2
for v,p) <- dice_sum(dp).view.zipWithIndex)
output(largest+step+p) += select_greater * v
for (d <- 2 until dice) {
dp -= 1
val leqv = lesser_or_equal(residual, prefix, d) * select_greater
for v,p) <- dice_sum(dp).view.zipWithIndex)
output(largest*d+step+p) += leqv * v
}
for (d <- 2 until dice)
dice_sum(d-1) = convolution(d, dice_sum(d-1
}
output.map(n => Rational(n, BigInt(dice)**length.slice(largest, dice*largest+1)
}
}
В инклюдах - тривиальная самописная табличка для предвычислений C(n,k) и внешняя библиотека spire, потому что встроенные библиотеки scala обделены поддержкой длинной арифметики.
Очевидно как расширить эту методику на произвольные распределения вероятностей, на выборку из окна, обрезанного с двух сторон, а не только снизу, как здесь, и любой монотонный метод сворачивания, а не только сумму.
Меня беспокоит получившая пятая степень. Как-то слишком быстро деградирует производительность с ростом задачи. Можно можно как-то по другому произвести декомпозицию получившихся вариантов, чтобы не приходилось так много циклов нарезать внутри?
Оставить комментарий
yroslavasako
Я хочу посчитать распределение суммы кубов с m равновесными сторонами, которые бросаются l раз и из них выбирается k больших кубов, которые и суммируются. Если спросите зачем - решил написать собственную монаду вероятности с преферансом и дамами, но споткнулся о проблему плохих свёрток, для которых и нашёл простой пример.Вот так это выглядит на anydice : http://anydice.com/program/2d10
К сожалению, сам anydice считает всё тупым перебором и потому заведомо справиться не может. Может кто придумает какой-нибудь полиноминальный алгоритм от количества кубов?