Вопрос по algorithm, math, random – Алгоритм генерации случайных чисел из дискретного распределения?

3

Design a fast algorithm to repeatedly generate numbers from the discrete distribution: Given an array a[] of non negative real numbers that sum to 1, the goal is to return index i with probability a[i]

Я нашел этот вопрос в интерактивной книге по алгоритмам, Введение в программирование на Java, глава 4.2: Сортировка и поиск (http://introcs.cs.princeton.edu/java/42sort/).

подсказка говорит:

Form an array s[] of cumulated sums such that s[i] is the sum of the first i elements of a[]. Now, generate a random real number r between 0 and 1, and use binary search to return the index i for which s[i] ≤ s[i+1].

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

Хм, так какa[] неотрицателен,s[i] <= s[i+1] верно для всехi, Намек кажется неправильным. Я думаю, что это означает, что вы должны вернуть первыйi такой, чтоs[i] >= r. IVlad
Что вы пробовали до сих пор, что не работает? Пожалуйста, опубликуйте свой код и объяснение того, как он работает не так, как вы ожидаете, и кто-то здесь будет рад помочь вам разобраться, как его исправить. Однако мы не просто делаем вашу работу за вас - вам нужно сделать какую-то работу, чтобы попытаться выяснить это самостоятельно. :) Ken White
возможный дубликатData structure for loaded dice? templatetypedef

Ваш Ответ

4   ответа
0

) целыми числами, а их сумма указана в узле-> childsum. Для максимальной скорости дети сортируются (более или менее) в порядке убывания. (ожидается, что веса будут иметь степенной закон распределения, только с несколькими высокими весами и многими меньшими)

    /*
     *          Choose a symbol at random from this context.
     *          weighted by ->thevalue
     */
    credit = urnd( node->childsum );
    for(cidx=0; 1; cidx = (cidx+1) % node->branch) {
        symbol = node->children[cidx].ptr->symbol;
        if (credit < node->children[cidx].ptr->thevalue) break;
        /* 20120203 if (node->children[cidx].ptr->thevalue == 0) credit--; */
        credit -= node->children[cidx].ptr->thevalue;
    }
done:
    // fprintf(stderr, "{+%u}", symbol );
    return symbol;
0

В зависимости от степени детализации вы можете создать индекс из 100, 1000 или 10000 элементов. Предположим, что распределение (a, b, c, d) с p = (10%, 20%, 30%, 40%), мы создаем карту:

val prob = Map ('a' -> 10, 'b' -> 20, 'c' -> 30, 'd' -> 40) 
val index = (for (e <- prob;
  i <- (1 to e._2)) yield e._1 ).toList 

index: List[Char] = List(a, a, a, a, a, a, a, a, a, a, 
b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, 
c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, c, 
d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d, d)

Теперь мы можем очень быстро выбрать элемент с желаемой вероятностью:

val x = index (random.nextInt (100))

х теперь на 40% д, на 10% а и так далее. Короткая настройка, быстрый доступ.

Числа даже не нужно суммировать до 100, но вы должны рассчитать диапазон один раз, а затем:

val max = prob.map (_._2).sum 
val x = index (random.nextInt (max))
8

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

Конкретный подход, который вы ищете, описан в разделе «Выбор колеса рулетки».

Надеюсь это поможет!

2

который реализует «колесо рулетки». Техника. Это трудно объяснить без графики. Статья, на которую ссылается templatetypedef, должна помочь. Также отметим, что этот алгоритм фактически не требует нормализации весов (им не нужно суммировать до 1), но, тем не менее, это будет работать.

import random

trials = 50
selected_indices = []

# weights on each index
distrib = [0.1, 0.4, 0.2, 0.3]

index = random.randrange(0, len(distrib) - 1)
max_weight = max(distrib)
B = 0
# generate 'trials' random indices
for i in range (trials):

    # increase B by a factor which is
    # guaranteed to be much larger than our largest weight
    B = B + random.uniform(0, 2 * max_weight)

    # continue stepping through wheel until B lands 'within' a weight
    while(B > distrib[index]):
        B = B - distrib[index]
        index = (index + 1) % len(distrib)
    selected_indices.append(index)

print("Randomly selected indices from {0} trials".format(trials))
print(selected_indices)

Похожие вопросы