Изменения

Перейти к: навигация, поиск

Получение номера по объекту

16 байт убрано, 02:41, 5 декабря 2014
Описание алгоритма
*<tex>d[i][j]</tex> - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)
'''functionint''' object2num(a: '''list <A>''')
numOfObject = 0
'''for''' i = 1 '''to''' n '''do''' ''// перебираем элементы комбинаторного объекта''
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого''
'''if''' элемент j можно поставить на i-e место
'''then''' numOfObject += d[i][j]
'''return''' numOfObject
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.
29
правок

Навигация