Изменения
Нет описания правки
numOfObject -= (количество комбинаторных обектов с данным префиксом)
'''} else {'''
break
'''}'''
'''}'''
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью. Приведем примеры способов получения некоторых из [[Комбинаторные объекты|комбинаторных объектов]] по номеру.
== Перестановки ==
Рассмотрим алгоритм получения <tex>i</tex>-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера <tex>n</tex>.
Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество перестановок не всевозможных суффиксов зависит только от префиксадлины) то есть можем просто посчитать "количество диапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:
*'''n!''' {{---}} количество перестановок размера <tex>n</tex>
alreadyWas = (numOfPermutation - 1) div (n-i)!
numOfPermutation = ((numOfPermutation - 1) mod (n-i)! ) + 1
теперь j-ый элемент занят (находится в нашем префиксе)
'''}'''
'''for''' i = 1 '''to''' n '''do'''
'''if''' numOfObject numOfBitvector > 2^(n-i) '''{''' numOfObject numOfBitvector -= 2^(n-i)
bitvector[i] = 1
'''} else {'''
