74
правки
Изменения
→Описание алгоритма
Пусть <tex> B = \{b_1, b_2 ..., b_k\} </tex> - множество различных элементов, которые могут находиться в данном комбинаторном объекте.
Будем получать элементы по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы построили префикс длинны <tex> i </tex> : <tex> I P = \{a_1, a_2, \ldots, a_i\} </tex>. Будем выбирать элемент <tex> a_{i+1} </tex> из множества всех возможных так, чтобы вероятность выбора элемнта <tex> b \in B </tex>, была пропорциональна числу комбинторных обьектов размера <tex> n </tex> с префиксом <tex> I P + b </tex>. Для этого разобъем отрезок натуральных чисел <tex> [1, s] </tex>. где <tex> s </tex> - число различных комбинаторных объектов с текущим префиксом, на <tex> k </tex> диапазонов так, чтобы размер диапазаоны <tex> d_j </tex> был равен числу объектов с префиксом <tex> I P + b_j </tex>. С помощью функция для генерации случайного числа получим число <tex> r </tex> в интервале <tex> [1, s] </tex> и добавим к префиксу <tex> I </tex> элемент <tex> b_j </tex> соответствующий диапазону отрезка в которм находится полученное число.
'''object''' randomObject(n: '''int''', k: '''int'''):<font color = green> // n {{---}} размер комбинторного объекта, k {{---}} число различных элемнтов.</font>
'''for''' i = 1 '''to''' n
s = number(prefix) <font color = green> // число комбинаторных объектов с текущим префиксом. </font>
r = random(1, s)
'''for''' j = 1 '''to''' k
'''if''' number(prefix + bB[j]) < r <font color = green> // b <tex> B </tex> {{---}} множество всех возможных элементов. </font> r = r - number(prefix + bB[j]) <font color = green> // если <tex> r </tex> не попало в текщий диапазон {{---}} перейдем к следующему.</font>
'''else'''
prefix[i] = b[j]
break
'''return''' prefix
