Category: 18+

Category was added automatically. Read all entries about "18+".

Прогерское: Палочный алгоритм генерации конечно распределённых случайных чисел

Задача на «Элементах»

На момент написания задача решение ещё не выложено, но я полностью решил её.

Задача. Есть n палок. Палки можно распиливать на части и склеивать в новые палки. Можно ли получить n палок одинаковой длины, чтобы каждая была склеена не более чем из двух кусочков?

Решение. Берём две палки: одна длиннее среднего, другая короче. От длинной отрезаем кусок и наращиваем им короткую. Получается «хорошая» палка, откладываем её в сторону. Продолжаем, пока палки не кончатся.

Тут снова должен быть троллейбус из буханки.

Стандартный алгоритм генерации случайных чисел любого распределения — F−1(ξ). Получить равномерно распределённое случайное число ξ и обработать обратной функцией распределения F−1.

Стандартными алгоритмами пользуются редко, поскольку функции распределения редко бывают элементарными. Конкретно для конечного распределения (1…n с вероятностями p1…pn) этот алгоритм плох тем, что функция F−1 кусочно-постоянная, и в общем случае поиск того куска, в который попала ξ(ω), занимает log n операций.

Можно придумать таблицу поиска, но если у нас два элемента «эпичного шмота», которые выпадают с вероятностью 1/100, эта самая таблица будет состоять минимум из 50 элементов — в то время как возможных исходов всего пять. А можно ли, перетасовав исходы, собрать таблицу поиска из пяти элементов? Оказывается, можно!

Пусть у нас есть n палок разных цветов. Длины — вероятности, цвета — возможные исходы. Уточним цифры: чёрная палка длины 0,78 («ничего не выпало»), зелёная и синяя по 0,1 («обычные шмотки»), красная и жёлтая по 0,01 («эпичные шмотки»). По нашему алгоритму новые палки будут такие: 1) Красный кусок длины 0,01, чёрный длины 0,19; 2) Такая же жёлто-чёрная; 3) Зелёный и чёрный по 0,1; 4) Такая же сине-чёрная; 5) Полностью чёрная палка длины 0,2.

Алгоритм генерации — выбрать палку, затем выбрать цвет из двух. Если нужно обойтись именно одним случайным числом — допустим, выпало 0,6789. Множим на 5 и получаем 3,xxx — берём предпоследнюю палку. На ней порог 0,7 — так что выпал синий кусок, то есть вторая из простых шмоток.

Если вероятности известны целыми долями, есть интересный способ. Но давайте добавим ещё одну эпичную шмотку с таким же шансом 1. Получаются доли 1, 1, 1, 10, 10 и 77. «Нормальной» длиной будет [100/6]=16, и палок будет семь штук: 1+15 (3 шт.), 10+6 (2 шт.), 16 и 4. Если выпало 32: 32/16=2 (имеем дело с 3-й палкой), 32 меньше порога 32+1=33 — выпала как раз наша новая эпичная!

Сборка таблицы поиска за O(n), генерация чисел за постоянное время.