3

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

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].

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

  • Что вы пробовали до сих пор, что не работает? Пожалуйста, опубликуйте свой код и объяснение того, как он работает не так, как вы ожидаете, и кто-то здесь будет рад помочь вам разобраться, как его исправить. Однако мы не просто делаем вашу работу за вас - вам нужно сделать какую-то работу, чтобы попытаться выяснить это самостоятельно. :)

    от Ken White
  • Хм, так какa[] неотрицателен,s[i] <= s[i+1] верно для всехi, Намек кажется неправильным. Я думаю, что это означает, что вы должны вернуть первыйi такой, чтоs[i] >= r.

    от IVlad
  • возможный дубликатData structure for loaded dice?

    от templatetypedef
  • 8

    Есть много способов ответить на эту проблему.

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

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

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

  • 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))
    

  • 0

    Это фрагмент от wakkerbot / megahal. Здесь веса являются (беззнаковыми

    ) целыми числами, а их сумма указана в узле-> 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;
    

  • 2

    Здесь представлен алгоритм Python

    который реализует «колесо рулетки». Техника. Это трудно объяснить без графики. Статья, на которую ссылается 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)