Случайное число для выбора победителей на основе вероятности

Question

Представьте, что у вас есть массив хэшей, представляющих конкурента и их вероятность выиграть приз (с плавающей точкой от 0 до 1).Как:

  [ {:name => "Adam" , :prob => 0.5}
    {:name => "Ben" , :prob => 1.0}
    {:name => "Chris" , :prob => 0.1}
    {:name => "Daniel" , :prob => 0.2}
    {:name => "Ed" , :prob => 0.7}
    {:name => "Frey" , :prob => 0.5}
    {:name => "Gilbert" , :prob => 0.3}
  ]

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

Общая вероятность выборки составляет 3,3

Логическим подходом будет вычисление случайного значения, например:

val = rand(33)/10.0

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

Этот подходработает, но это предполагает сканирование в массиве.

Интересно, будет ли более простое решение.Есть идеи?

PS: представьте, что массив может содержать большое количество элементов.

Answer 1

Создайте цикл, который будет работать до 3 победителей.В этом цикле сгенерируйте конкретное случайное число, используя любой случайный метод, доступный на выбранном вами языке программирования.После этого начните перебирать пользователей.Если вероятность какого-либо пользователя меньше этого случайного числа, примите его как победителя.Если на любой итерации цикла победитель не выбран, например, в случае, когда самая низкая вероятность в вашем списке равна 0,2, а сгенерированное случайное число равно 0,1, в этом случае переходите к следующей итерации цикла.Выйдите из цикла, когда вы получите 3 победителей.Возможный псевдокод для такого может быть следующим:

int count=0;
while(count<3){
    temp=GenerateRandomNumber()
    int userIndex= AcceptWinner(UserListProbability,temp)
    //here keep iterating through the users to check which user's probability is less than temp and returns the index of the winner in the List

    if(userIndex==-1)//No winner selected
        continue;
    else{
        count++;
        Print List(userIndex)
    }
}

Примечание: список должен быть отсортирован

Answer 2

Я думал об этом и думаю, что мой результат имеет смысл:

1. отсортировать вектор по вероятности: [a = 0,1, b = 0,2, c = 0,3, d = 0,4]
2. выберите случайное число (например, 0,5)
3. итерация с начала и суммирование значений вероятности и остановка, когда она выше: ответ = 0,1 + 0,2 + 0,3. Итак, 0.6> 0.5, мы ценим 'c'

Суть в том, что значения в конце вектора должны иметь более высокую вероятность выбора. Я реализовал в Python:

values = [0.1,0.2,0.3,0.4]
count_values = len(values)*[0]
answer = len(values)*[0]

iterations = 10000 

for i in range(0,iterations):
    rand = float(random.randint(0,iterations))/iterations
    count = 0
    sum = 0
    while sum <= rand and count <= len(values):
        sum += values[count]
        count += 1
    count_values[count-1]+=1

for i in range(0,len(count_values)):
    answer[i] = float(count_values[i])/iterations

и, выполнив несколько раз, я вычислил вероятность выбора всех элементов, которые должны соответствовать нашей начальной вероятности:

[0.1043, 0.196, 0.307, 0.3927]
[0.1018, 0.2003, 0.2954, 0.4025]
[0.0965, 0.1997, 0.3039, 0.3999]

Answer 3

Существует также подход, который работает сегодня, но имеет некоторые проблемы.

Сегодня я создаю массив и помещаю вероятность * 100 записей для каждого человека в этом массиве.

Затемможно сделать случайный выбор непосредственно для содержимого массива.

Первая проблема заключается в том, что это дорого для каждого аспекта (память, обработка, ...) и не масштабируется.

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

Тем не менее, для небольших наборов данных (как у меня до сих пор)но со временем будет увеличиваться), это решение отлично работает.

Answer 4

Я предполагаю, что в вашем примере "вероятность" означает "вес" (таким образом, люди с вероятностью 1,0 не гарантированно выиграют, а общая вероятность не составит 1,0)

Вы можете построить дерево узлов, где конечные узлы содержали ваши отдельные записи:

leaf1 = {:name => "Adam" , :prob => 0.5}
leaf2 = {:name => "Ben" , :prob => 1.0}

и каждый узел содержал сумму узлов под ним

node1 = { :prob_sum => 1.5 , :children=> [ leaf1, leaf2] }

Корневой узел тогда содержит сумму всей структуры

root_node = { :prob_sum => 33 , :children => [ leaf9, leaf10] }

Затем вы выбираете случайное число от нуля до суммы, содержащейся в корневом узле.

my_random = rand( root_node.prob_sum )

Тогда пройдите через дерево. Каждый узел содержит сумму всех узлов под ним, поэтому, если ваше случайное число больше, чем узел, вы вычитаете значение этого узла и пропускаете эту ветвь.

def find_node( my_random ):
c = children.first()
while( c ):
     if ( c.prob_sum < my_random ):
         return c.find_node(my_random)
     my_random -= c.prob_sum
     c = c.next

Предполагая, что вы построили сбалансированное дерево, вы должны получить результаты в O (log n)

В качестве альтернативы, вы можете получить тот же результат, добавив поле промежуточного итога к вашему текущему набору данных и выполнив бинарный поиск на основе этого промежуточного итога. Это, вероятно, будет проще реализовать, но будет применимо, только если ваш рабочий набор может поместиться в памяти.