Изменения
Нет описания правки
*<tex>\mathtt{k}</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2</tex>, поскольку возможны только <tex>0</tex> и <tex>1</tex>. Все элементы занумерованы в лексикографическом порядке, начиная с <tex>1</tex>.
Комбинаторные объекты занумерованы с <tex>0</tex>. Переход к нумерации с единицы можно сделать с помощью одной операции декремента перед проходом алгоритма.
'''function''' num2object(numOfObject: '''int'''):
'''for''' i = 1 '''to''' n
'''for''' j = 1 '''to''' k
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью.
Приведем примеры получения некоторых [[Комбинаторные объекты|комбинаторных объектов]] по номеру.
== Битовые вектора ==
Рассмотрим алгоритм получения <tex>k</tex>-ого в лексикографическом порядке битового вектора размера <tex>n</tex>.
При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия:
*<tex>\mathtt{bitvector[n]}</tex> {{---}} искомый битовый вектор
*<tex>\mathtt{numOfBitvector}</tex> {{---}} номер искомого вектора среди всех битовых векторов
*<tex>\mathtt{pow(2, n)}</tex> {{---}} <tex>2^{n}</tex> количество битовых векторов длины <tex>n</tex>
'''vector<int>''' num2bitvector(numOfBitvector: '''int'''):
'''for''' i = 1 '''to''' n '''do'''
'''if''' numOfBitvector >= pow(2, (n - i))
numOfBitvector -= pow(2, (n - i))
bitvector[i] = 1
'''else'''
bitvector[i] = 0
'''return''' bitvecor
Данный алгоритм работает за <tex>O(n)</tex>, так как в случае битовых векторов <tex>k</tex> не зависит от <tex>n</tex>.
== Перестановки ==
*<tex>\mathtt{curFree}</tex> {{---}} если элемент с номером <tex>j</tex> свободен, то он имеет номер curFree среди всех свободных элементов с <tex>1</tex> по <tex>j</tex>
'''functionlist<int>''' num2permutation(k: '''int'''):
'''for''' i = 1 '''to''' n '''do'''
alreadyWas = k div (n-i)! k = k mod (n-i)!
curFree = 0
'''for''' j = 1 '''to''' n
'''if''' was[j] == ''false ''
curFree++
'''if''' curFree == alreadyWas + 1
множества за <tex>O( \log {n}) </tex>.
== Битовые вектора Сочетания ==Рассмотрим алгоритм получения На каждой итерации мы проверяем, входит ли число <tex>next</tex> в искомое сочетание. Если мы хотим взять <tex>next</tex>, то номер перестановки должен быть меньше, чем <texdpi=140>\binom{n - 1}{k- 1}</tex>, так как потом надо будет выбрать <tex>k -ого в лексикографическом порядке битового вектора размера 1</tex> элемент из <tex>n- 1</tex>доступных.При построении битовых векторов можно не проверять условие возможности постановки какого-Если нет, то объекта на текущее место. На каждый позиции может стоять один из двух элементовбудем считать, независимо от тогочто <tex dpi=140>\binom{n - 1}{k - 1}</tex> перестановок, какие элементы находятся в префиксеначинающихся с <tex>next</tex>, мы пропустили. В обоих случаях рассмотрение текущего числа <tex>next</tex> мы заканчиваем и переходим к следующему числу. Так как у нас всего два возможных элемента, упростим второй цикл до условия: *<tex>\mathtt{bitvector[n]choose}</tex> {{---}} искомый битовый векторискомое сочетание,*<tex>\mathtt{numOfBitvectorC[n][k]}</tex> {{---}} номер искомого вектора среди всех битовых векторовколичество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,
== См. также ==
*[[Получение номера по объекту|Получение номера по объекту]]
