Генерировать случайное взвешенное значение

Поскольку я застрял дома сегодня из-за гриппа 🙁 Я решил попробовать и понять это для вас. По сути, то, что вы просите, это своего рода интерполяция. Я использовал самые простые (линейные), и это мои результаты и код. Код довольно грязный, и я могу исправить его в ближайшие дни ..

 <?php // this function interpolates $a to $b over $steps steps, starting from key $k // this can be cleaned up significantly function interpolate($a, $b, $steps, $k) { @$per_step = abs($a - $b)/$steps; // suppress warnings in case of division by zero if ($a > $b) $decreasing = true; else $decreasing = false; $final = array(); for ($i = 1; $i <= $steps-1; ++$i) { if ($decreasing) $final[$i+$k] = $a-=$per_step; // linear interpolation else $final[$i+$k] = $a+=$per_step; // linear interpolation } return $final; } // this function combines probability arrays after the interpolation occurs // this may happen multiple times, think about 1, 3, 5. interpolation would have to occur // from 1 -> 2 -> 3, and from 3 -> 4 -> 5. function interpolateProbabilities ($nodes) { $pNodes = array(); $pNodes = $nodes; $keys = array_keys($nodes); for ($i = 0; $i < count($keys); $i++) { if ($keys[$i+1] - $keys[$i] != 1) { $pNodes += interpolate($nodes[$keys[$i]], $nodes[$keys[$i+1]], $keys[$i+1] - $keys[$i], $keys[$i]); } } ksort($pNodes); return $pNodes; } // this generates a weighed random value and is pretty much copy-pasted from: // http://w-shadow.com/blog/2008/12/10/fast-weighted-random-choice-in-php/ // it's robust and re-writing it would be somewhat pointless function generateWeighedRandomValue($nodes) { $weights = array_values($nodes); $values = array_keys($nodes); $count = count($values); $i = 0; $n = 0; $num = mt_rand(0, array_sum($weights)); while($i < $count) { $n += $weights[$i]; if($n >= $num) { break; } $i++; } return $values[$i]; } // two test cases $nodes = array( 1 => 12, 5 => 22, 9 => 31, 10 => 35); // test 1 $nodes = array( 1 => 22, 3 => 50, 6 => 2, 7 => 16, 10 => 10); // test 2 $export = array(); // run it 1000 times for ($i = 0; $i < 1000; ++$i) { $export[generateWeighedRandomValue(interpolateProbabilities($nodes))]++; } // for copy-pasting into excel to test out distribution print_r($export); ?> 

Результаты, я думаю, именно то, что вы ищете. В случае:

 $nodes = array( 1 => 12, 5 => 22, 9 => 31, 10 => 35); // test 1 

Я получил следующий (окончательный) массив:

 Array ( [5] => 92 [7] => 94 [10] => 162 [8] => 140 [3] => 71 [6] => 114 [2] => 75 [4] => 69 [9] => 131 [1] => 52 ) 

А именно: 1 должно произойти 12% времени, 5 22%, 9 31% и 10 35% времени. Давайте нарисуем его:

Это выглядит многообещающе, но позволяет попробовать что-то более сумасшедшее …

 $nodes = array( 1 => 22, 3 => 50, 6 => 2, 7 => 16, 10 => 10); // test 2 

В этом случае 3 должно происходить в 50% случаев и круто уменьшаться до 6 . Давай посмотрим что происходит! Это массив (в ретроспективе, я должен был отсортировать эти массивы):

 Array ( [4] => 163 [7] => 64 [2] => 180 [10] => 47 [1] => 115 [5] => 81 [3] => 227 [8] => 57 [6] => 6 [9] => 60 ) 

И давайте посмотрим на картинку:

Похоже, это работает 🙂

Надеюсь, я смог решить вашу проблему (или, по крайней мере, указать вам в правильном направлении). Обратите внимание, что мой код в настоящее время имеет ряд условий. А именно, исходные узлы, которые вы предоставляете, ДОЛЖНЫ иметь вероятности, которые составляют до 100%, или вы можете получить какое-то неудобное поведение.

Кроме того, код довольно грязный, но концепции относительно просты. Некоторые другие интересные вещи – попытаться вместо использования линейной интерполяции использовать другой вид, который даст вам более интересные результаты!

Алгоритм

Чтобы избежать путаницы, я просто покажу, как работает алгоритм. Я даю PHP массив $node который находится в виде integer => frequency in percentage и заканчивается тем, что выглядит как array( 1 => 22, 3 => 50, 6 => 2, 7 => 16, 10 => 10) , который является test 2 сверху.

Test 2 основном говорит, что вы хотите, чтобы 5 контрольных узлов были размещены на 1, 3, 6, 7, and 10 с частотой 22%, 50%, 2%, 16%, and 10% соответственно. Во-первых, мне нужно посмотреть, где именно мне нужно сделать интерполяцию. Например, мне не нужно делать это между 6 и 7 , но мне нужно сделать это между 1 и 3 (нам нужно интерполировать 2 ) и 7 и 10 (где нам нужно интерполировать 8 и 9 ).

Интерполяция между 1 -> 3 имеет (3 - 1) - 1 = 1 шаг и должна быть вставлена ​​в key[2] в исходном массиве. Значение ( % ) для интерполяции 1 -> 3 – abs($a - $b) / $steps которое переводится в абсолютное значение % от 1 минус % от 2 , деленное на steps + 1 которые в нашем случай, оказывается равным 14 . Нам нужно увидеть, увеличивается или уменьшается функция (hello Calculus). Если функция увеличивается, мы добавляем шаг % к новому массиву интерполяции, пока не наполним все наши пустые точки (если функция уменьшается, мы вычитаем значение шага % value . Поскольку нам нужно только заполнить одно место, мы возвращаем 2 => 36 ( 22 + 14 = 36 ).

Мы объединяем массивы, и результат равен (1 => 22, 2 => 36, 3 => 50, 6 => 2, 7 => 16, 10 => 10) . Программа интерполировала 2 , что было процентным значением, которое мы явно не объявляли.

В случае 7 -> 10 существует 2 шага, процентный шаг 2 который исходит из (16-10) / (3 + 1) = 2 . Функция уменьшается, поэтому нам нужно дважды вычесть 2 . Конечный интерполированный массив равен (8 => 14, 9 => 12) . Мы объединяем все массивы и вуаля.

На следующем рисунке показаны зеленые (начальные значения) и красные (интерполированные значения). Возможно, вам придется «просмотреть изображение», чтобы ясно видеть все это. Вы заметите, что я использую ± поскольку алгоритм должен выяснить, должны ли мы увеличиваться или уменьшаться в течение определенного периода времени.

Этот код, вероятно, должен быть написан в более сложной парадигме ООП. Я много играю с ключами массива (например, мне нужно передать $k поэтому проще объединить массивы, как только я верну их из interpolate($a, $b, $steps, $k) потому что они автоматически имеют нужные ключи. Это просто особенность PHP, и в ретроспективе я, вероятно, должен был начать с более читаемого подхода ООП.

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

Test 1 Test 2

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

На этом графике я взвешивал 1 = > 1, 5 => 98, 10 => 1 и вы видите крайности эффекта увлажнения. В конце концов, проценты, по определению, должны составлять до 100! Просто важно понять, что эффект увлажнения прямо пропорционален количеству шагов между крайностями.

Предполагая, что вы можете справиться с целыми числами для процентов, просто назначьте каждое значение от 0 до 99 результата – например, 0-9 может иметь результат 1 и 95-99, может иметь результат 6 (чтобы дать 10% = 1 и 5% = 6). Когда у вас есть эта функция перевода (однако вы достигаете этого – существуют различные подходы, которые вы можете использовать) вам просто нужно создать случайное число в диапазоне 0-99 и перевести его в результат.

Ваш вопрос не совсем ясен с точки зрения кода, который вы хотите (или даже на каком языке – C # или PHP?), Но, надеюсь, это поможет.

Вот код C #, который позволит вам получить какой-либо уклон, который вам нравится, в разумных пределах – вам не нужно выражать его в процентах, но вы можете сделать:

 static int BiasedRandom(Random rng, params int[] chances) { int sum = chances.Sum(); int roll = rng.Next(sum); for (int i = 0; i < chances.Length - 1; i++) { if (roll < chances[i]) { return i; } roll -= chances[i]; } return chances.Length - 1; } 

Так, например, вы можете использовать

 int roll = BiasedRandom(rng, 10, 10, 10, 10, 10, 50) + 1; 

что даст 10% шанс для каждого из 1-5 и 50% шанс получить 6.

Быстрый и грязный способ в C #:

 T PickWeightedRandom<T>(IEnumerable<Tuple<T,double>> items, Random r) { var sum = 0.0; var rand = r.NextDouble(); return items.First(x => { sum += x.Item2; return rand < sum; }).Item1; } 

Тестовый код:

 var values = new [] { Tuple.Create(1, 0.05), Tuple.Create(2, 0.15), Tuple.Create(3, 0.3), Tuple.Create(4, 0.3), Tuple.Create(5, 0.15), Tuple.Create(6, 0.05), }; const int iterations = 1000; var counts = new int[values.Length]; var random = new Random(); for (int i = 0; i < iterations; i++) { counts[PickWeightedRandom(values, random)-1]++; } foreach (var item in counts) { Console.WriteLine(item/(double)iterations); } 

Выход (с итерациями = 1000000):

 0.050224 0.150137 0.300592 0.298879 0.150441 0.049727 

Выглядит как:

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

 function random($density, $max) { do { $rand = lcg_value(); $rand2 = lcg_value() * $max; } while ($density($rand) < $rand2); return $rand; } 

$density – функция плотности, принимающая число с плавающей запятой между нулем и одним аргументом и возвращающее значение меньше $max . Для вашего примера эта функция плотности может быть:

 $density = function($x) { static $values = array( 1 => 0.05, 2 => 0.15, 3 => 0.30, 4 => 0.30, 5 => 0.15, 6 => 0.05, ); return $values[ceil($x * 6)]; }; 

Примером может служить следующий вызов:

 ceil(random($density, 0.3) * 6); // 0.3 is the greatest value returned by $density // round and * 6 are used to map a 0 - 1 float to a 1 - 6 int. 

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

PS: Вышеприведенная реализация является общей и, следовательно, использует случайное значение от 0 до 1. Создавая функцию, которая работает только для вашего подхода, все становится проще:

 function random() { static $values = array( 1 => 0.05, 2 => 0.15, 3 => 0.30, 4 => 0.30, 5 => 0.15, 6 => 0.05, ); do { $rand = mt_rand(1, 6); $rand2 = lcg_value() * 0.3; } while ($values[$rand] < $rand2); return $rand; } random(); 

Сначала вам нужно охарактеризовать ваш генератор случайных чисел. В случае PHP функция rand () возвращает хороший плоский профиль – поэтому предварительной обработки не требуется.

Перестройте функцию распределения выходных данных, так что область под ней равна единице, а диапазон начинается с нуля. Затем вычислите его интеграл. Храните интеграл (например, в виде массива значений). Затем, когда вам понадобится случайное число matchnig профиля, сначала получите случайное число от 0 до 1 от встроенного генератора, затем найдите координату Y в интеграле, где координата X – это значение, которое вы создали. Наконец, масштабируйте значение до требуемого диапазона (например, если вы ищете значение от 0 до 10, умножьте на 10, если ищете значение от -8 до +8, забрюйте на 16 и вычтите 8).

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

Я не пробовал, но я думаю, что это может сработать:

 $random($probability) { $rnd = rand() / getrandmax(); foreach($probability as $num => $prob) { $rnd -= $prob; if($rnd <=0) return $num; } return -1; //this should never happen } 

И назовите это так (используя ваш второй пример):

 $distribution = array( 1 => 0.10, 2 => 0.15, 3 => 0.30, 4 => 0.27, 5 => 0.14, 6 => 0.04); $number = random($distribution);