48
правок
Изменения
Нет описания правки
Следующий алгоритм вычисляет эту сумму
*numOfObject {{---}} искомый номер комбинаторного объекта.
*a[1..n] {{---}} данный комбинаторный обьект, состоящий из элементов множества <tex>A</tex>.
*d[i][j] - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Для битового вектора <tex>k=2</tex>: возможны только 0 и 1. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.
*was[1..n] {{---}} использовали ли мы уже эту цифру в перестановке.
''меньше нашего в лексикографическом порядке, идут раньше данной перестановки
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.
*numOfBitvector {{---}} искомый номер вектора.
*bitvector[1..n] {{---}} данный вектор.
'''function''' NumOfBitvectorFunc(bitvector: '''Binary''') '''for''' i = 1 '''to''' n '''do''' '''if''' bitvector[i] == 1 numOfBitvector += 2 ** (n - i) '''return''' numOfBitvector
== См. также ==