Взвешенные случайные целые числа

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

  0  |  1  |  2  |  3  |  4  |  5  |  6
─────────────────────────────────────────
  X  |  X  |  X  |  X  |  X  |  X  |  X
  X  |  X  |  X  |  X  |  X  |  X  |   
  X  |  X  |  X  |  X  |  X  |     |   
  X  |  X  |  X  |  X  |     |     |   
  X  |  X  |  X  |     |     |     |   
  X  |  X  |     |     |     |     |   
  X  |     |     |     |     |     |

Какой самый эффективный способ сделать это?


c random math weighted
person Max    schedule 21.10.2012    source источник
comment
Если вы двигаетесь полностью вправо (то есть к 6), независимо от того, где вы начинаете, то 6 всегда будет посещено, да? Это означает, что 6 всегда будет выбросом. Пожалуйста, уточните свой вопрос.   -  person aecolley    schedule 21.10.2012
comment
данный дистрибутив будет создан, если вы всегда выбираете «0»...   -  person mfrankli    schedule 21.10.2012
comment
в качестве альтернативы опишите реальную проблему, которую вы пытаетесь решить, а не предполагаемое решение...   -  person Mitch Wheat    schedule 21.10.2012
comment
@aecolley Ты прав, я должен был это заметить. Изменено.   -  person Max    schedule 21.10.2012
comment
Я не думаю, что то, что вы описываете, возможно. Единственный вес, который будет равномерно распределять посещения, — это всегда выбирать «0». Когда вы выбираете 0, вы добавляете 1 счет ко всему. Если выбрать 0 N раз и 5 1 раз, то получится 0,1,2,3,4 -> N, а еще посещали на 5 чаще.   -  person FoolishSeth    schedule 21.10.2012
comment
@FoolishSeth Вы правы, я не описал это должным образом. Поправлю вопрос..   -  person Max    schedule 21.10.2012

Ответы (3)


arrow_upward
3
arrow_downward

Ответ @Kerrek хорош.

Но если гистограмма весов состоит не только из маленьких целых чисел, вам нужно что-то более мощное:

Разделите [0..1] на интервалы, размер которых соответствует весам. Здесь вам нужны сегменты с относительным соотношением размеров 7:6:5:4:3:2:1. Таким образом, размер одной единицы интервала равен 1/(7+6+5+4+3+2+1)=1/28, а размеры интервалов равны 7/28, 6/28, ... 1/. 28.

Они составляют распределение вероятностей, поскольку их сумма равна 1.

Теперь найдем кумулятивное распределение:

P        x
7/28  => 0
13/28 => 1
18/28 => 2
22/28 => 3
25/28 => 4
27/28 => 5
28/28 => 6

Теперь сгенерируйте случайное число r в [0..1] и найдите его в этой таблице, найдя наименьшее x такое, что r <= P(x). Это случайное значение, которое вы хотите.

Поиск в таблице можно выполнить с помощью бинарного поиска, что является хорошей идеей, когда гистограмма имеет много интервалов.

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

person Gene    schedule 21.10.2012
comment
Спасибо за указание на обратную кумулятивную функцию плотности, которая привела меня к этому people.sc.fsu.edu/~jburkardt/c_src/asa241/asa241.c исходный код, который я думаю использовать. - person Max; 21.10.2012
comment
Собственно, о чем я, просто нужна некоторая интеграция. Что-то вроде 7x-(x^2)/2 = 6. Спасибо, что указали мне правильное направление. - person Max; 21.10.2012

arrow_upward
3
arrow_downward

Если ваш массив небольшой, просто выберите uniform случайный индекс в следующем массиве:

int a[] = {0,0,0,0,0,0,0, 1,1,1,1,1,1, 2,2,2,2,2, 3,3,3,3, 4,4,4, 5,5, 6};

Если вы хотите создать дистрибутив во время выполнения, используйте std::discrete_distribution.

person Kerrek SB    schedule 21.10.2012
comment
Массив большой, и его длина определяется только во время выполнения. - person Max; 21.10.2012
comment
@Alec: добавлено (хотя я не уверен, почему вы не описываете свои ограничения в вопросе). - person Kerrek SB; 21.10.2012

arrow_upward
0
arrow_downward

Чтобы получить желаемый дистрибутив, сначала вы в основном суммируете количество X, которое вы там написали. Вы можете сделать это так (мой C очень ржавый, так что относитесь к этому как к псевдокоду)

int num_cols = 7; // for your example
int max;
if (num_cols % 2 == 0) // even
{
    max = (num_cols+1) * (num_cols/2);
}
else // odd
{
    max = (num_cols+1) * (num_cols/2) + ((num_cols+1)/2);
}

Затем вам нужно случайным образом выбрать целое число от 1 до max включительно.

Итак, если ваше случайное целое число равно r, последний шаг — найти, какой столбец содержит r-й X. Что-то вроде этого должно работать:

for(int i=0;i<num_cols;i++)
{
    r -= (num_cols-i);
    if (r < 1) return i;
}
person FoolishSeth    schedule 21.10.2012