74
правки
Изменения
→Описание алгоритма
== Описание алгоритма ==
{{Задача
|definition = Необходимо сгенерировать случайный комбинаторный объект размера <tex> n </tex> чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.
}}
Пусть <tex> B = \{b_1, b_2 ..., b_k\} </tex> - множество различных элементов, которые могут находиться в данном комбинаторном объекте.
Будем получать элементы по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы построили префикс длинны <tex>i</tex>: <tex>\{a_1, a_2, \ldots, a_i\}</tex>. Будем выбирать элемент<tex>a_{i+1}</tex> из множества всех возможных так, чтобы вероятность выбора элемнта <tex>b_j</tex>, была пропорциональна числу комбинторных обьектов размера <tex> n </tex> с префиксом <tex>\{a_1, a_2, \ldots, a_i, b_j\}</tex>. Для этого разобъем отрезок чисел <tex>[1, s\]\subset\mathbb</tex>
