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

Question

Получил этот вопрос из руководства по разработке алгоритмов Стивена Скиена.

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

Answer 1

Когда 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

Answer 2

как то так

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 и т. Д.

Answer 3

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

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

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

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

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

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

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