Выбор чисел из набора с равной вероятностью

Получил этот вопрос из руководства по разработке алгоритмов от Steven Skiena.Выбор чисел из набора с равной вероятностью

Требуется выбрать значения k (значение) для формирования подмножества S 'из заданного множества S, содержащего n чисел, так что вероятность выбора для каждого числа равна (k/n). n неизвестно (я думал взять S как список ссылок для этого). также, мы можем иметь проходить только через множества S.

источник

2011-12-15 S..K

По существу такой же, как http://stackoverflow.com/questions/5416567/random-selection/5417178 # 5417178 –

Я думаю, что проблема другая, потому что n неизвестно. – xdavidliu

Нечто подобное

for elem in S 
    if random() < (k - S'.size)/S.size // This is float division 
    S'.add(elem)

Первый элемент выбирается с вероятностью k/n, второй с (n-k)/n * k/(n-1) + k/n * (k-1)/(n-1), которая сводится к k/n и т.д.

источник

2011-12-15 07:57:43

В соответствии с приведенной формулой вы должны учитывать индекс i элемента elem (начиная с 1), следовательно, иметь random() <(k - S'.size)/(S.size - i) // Float раздел – Alec

Этот ответ не работает, если S.size неизвестно, что является условием, указанным в исходном вопросе – xdavidliu

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

Когда n неизвестно Вам нужен нужный он-лайн алгоритм для так называемого Отбор проб коллектора. представлены здесь

Хорошие объяснения & доказательства эскизы http://propersubset.com/2010/04/choosing-random-elements.html

Я имею в виду этот алгоритм, реализованный в Python (из приведенной выше ссылке)

import random 
def random_subset(iterator, K): 
    result = [] 
    N = 0 

    for item in iterator: 
     N += 1 
     if len(result) < K: 
      result.append(item) 
     else: 
      s = int(random.random() * N) 
      if s < K: 
       result[ s ] = item 

    return result

источник

2012-05-04 13:34:51 Alec

Вы должны выбрать алгоритм, который действительно может имитировать реальный «Случайно выбирайте k чисел из n чисел». Ваш алгоритм должен иметь два свойства:

(1) Он должен вернуть k номеров в конце.

(2) Он должен действительно имитировать эти свойства целевой деятельности: каждое число выбирается с вероятностью k/n.

Oborok s answer is wrong because it hasn t первый объект.

for i = 0 to n 
randomly choose an integer number between [1,n-i+1] 
if [randomValue <= (k - S'.size)/(S.size - i + 1)] then 
    S'.add(S[i])

С выше плана выбора, каждое число выбирается с вероятностью к/n.You можно видеть, что, доказать ниже уравнением:

https://www.facebook.com/photo.php?fbid=677984275648191&l=7cafe5d468

источник

2014-10-09 17:35:04

Выбор чисел из набора с равной вероятностью

ответ

Смежные вопросы