48
правок
Изменения
Нет описания правки
*k {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Для битового вектора <tex>k=2</tex> : возможны только 0 и 1. Все элементы занумерованы в лексикографическом порядке, начиная с 1.
Комбинаторные объекты занумерованы с 0. Переход к нумерации с единицы можно сделать с помощью одной операции декремента перед проходом алгоритма.
'''function''' NumToObjectFunc(numOfObject) '''for''' i = 1 '''to''' n '''do''' '''for''' j = 1 '''to''' k '''do''' '''if''' j-ый элемент можно поставить на i-e место '''if''' numOfObject >= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i) numOfObject -= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i) '''else''' object[i] = j '''return''' object
Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью.
Приведем примеры получения некоторых [[Комбинаторные объекты|комбинаторных объектов]] по номеру.
*curFree {{---}} если элемент с номером <tex>j</tex> свободен, то он имеет номер curFree среди всех свободных элементов с 1 по <tex>j</tex>
'''function''' NumToPermutationFunc(k) '''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 permutation[i] = j was[j] = true '''return''' permutation
Данный алгоритм работает за <tex>O(n^2)</tex>, так как в случае перестановок <tex>n=k</tex>. Мы можем посчитать все n! за <tex>O(n) </tex>. Асимптотику можно улучшить
== Битовые вектора ==
Рассмотрим алгоритм получения <tex>ik</tex>-ого в лексикографическом порядке битового вектора размера <tex>n</tex>.
При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия:
*bitvector[n] {{---}} искомый битовый вектор
*2^n numOfBitvector {{---}} <tex>2^{n}</tex> количество номер искомого вектора среди всех битовых векторов длины <tex>n</tex>
*pow(2, n) {{---}} <tex>2^{n}</tex> количество битовых векторов длины <tex>n</tex> '''function''' NumToBitvectorFunc(numOfBitvector) '''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>.
== См. также ==
