48
правок
Изменения
Нет описания правки
*d[i][j] - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)
'''function''' NumOfObjectsFuncobject2num(a: '''list <A>''')
numOfObject = 0
'''for''' i = 1 '''to''' n '''do''' ''// перебираем элементы комбинаторного объекта''
'''then''' numOfObject += d[i][j]
'''return''' numOfObject
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Для Например, для битового вектора <tex>k=2</tex>: (возможны только 0 и 1). Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.
*was[1..n] {{---}} использовали ли мы уже эту цифру в перестановке.
'''function''' NumOfPermutationFuncpermutation2num(a: '''list <Aint>''') numOfPermutation = 0
'''for''' i = 1 '''to''' n '''do''' ''// n - количество элементов в перестановке''
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элемент, лексикографически меньший нашего, который может стоять на i-м месте
*bitvector[1..n] {{---}} данный вектор.
'''function''' NumOfBitvectorFuncbitvector2num(bitvector: '''Binarylist <int>''') numOfBitvector = 0
'''for''' i = 1 '''to''' n '''do'''
'''if''' bitvector[i] == 1
numOfBitvector += pow(2 ** (, n - i)
'''return''' numOfBitvector
== Скобочные последовательности ==
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D1%80%D0%B0%D0%B2%D0%B8%D0%BB%D1%8C%D0%BD%D1%8B%D0%B5_%D1%81%D0%BA%D0%BE%D0%B1%D0%BE%D1%87%D0%BD%D1%8B%D0%B5_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D0%B8#.D0.9F.D0.BE.D0.BB.D1.83.D1.87.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BD.D0.BE.D0.BC.D0.B5.D1.80.D0.B0_.D0.BF.D0.BE.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8 Получение номера правильной скобочной последоватеьности]
== См. также ==
*[[Получение объекта по номеру|Получение объекта по номеру]]
