Методы получения случайных комбинаторных объектов

Описание алгоритма

Задача:

Необходимо сгенерировать случайный комбинаторный объект размера [math] n [/math] с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.

Пусть [math] B = \{b_1, b_2 ..., b_k\} [/math] - множество различных элементов, которые могут находиться в данном комбинаторном объекте.

Будем получать элементы по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы построили префикс длинны [math]i[/math]: [math]\{a_1, a_2, \ldots, a_i\}[/math]. Будем выбирать элемент [math]a_{i+1}[/math] из множества всех возможных так, чтобы вероятность выбора элемнта [math]b_j[/math], была пропорциональна числу комбинторных обьектов размера [math] n [/math] с префиксом [math]\{a_1, a_2, \ldots, a_i, b_j\}[/math]. Для этого разобъем отрезок чисел [math][1, s\]\subset\mathbb[/math]