Изменения

Будем получать элементы по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы построили префикс длинны <tex> i </tex> : <tex> P = \{a_1, a_2, \ldots, a_i\} </tex>. Будем выбирать элемент <tex> a_{i+1} </tex> из множества всех возможных так, чтобы вероятность выбора элемнта <tex> b \in B </tex>, была пропорциональна числу комбинторных обьектов размера <tex> n </tex> с префиксом <tex> P + b </tex>. Для этого разобъем отрезок натуральных чисел <tex> [1, s] </tex>. где <tex> s </tex> - число различных комбинаторных объектов с текущим префиксом, на <tex> k </tex> диапазонов так, чтобы размер диапазаоны <tex> d_j </tex> был равен числу объектов с префиксом <tex> P + b_j </tex>. С помощью функция для генерации случайного числа получим число <tex> r </tex> в интервале <tex> [1, s] </tex> и добавим к префиксу <tex> I P </tex> элемент <tex> b_j </tex> соответствующий диапазону отрезка в которм находится полученное число.

Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью.