Изменения
Исправил опечатку с $$
== Описание алгоритма ==
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). Следующий алгоритм вычисляет эту сумму:*<tex>\mathtt{numOfObject }</tex> {{---}} искомый номер комбинаторного объекта.,*<tex>\mathtt{a[1..n] }</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>.,*<tex>\mathtt{d[i][j] }</tex> {{--- (}} количество комбинаторных объектов с префиксом от <tex>1 </tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>),
'''functionint''' NumOfObjectsFuncobject2num(a: '''list <A>''') :
numOfObject = 0
'''for''' i = 1 '''to''' n '''do''' '' <font color=green>// перебираем элементы комбинаторного объекта''</font> '''for''' j = 1 '''to''' a[i] - 1 '''do''' '' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше меньшие рассматриваемого'' </font> '''if''' элемент <tex>j </tex> можно поставить на <tex>i</tex>-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>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.
== Битовые вектора ==
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.
Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>.
На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>:
*<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,
'''int''' bitvector2num(bitvector: '''list<int>'''):
numOfBitvector = 0
'''for''' i = 1 '''to''' n
'''if''' bitvector[i] == 1
numOfBitvector += <tex>2^{n-i}</tex>
'''return''' numOfBitvector
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.
== Перестановки ==
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.,*P<tex>\mathtt{a[1..n] }</tex> {{---}} количество перестановок данного размера.данная перестановка,*a<tex>\mathtt{P[1..n] }</tex> {{---}} данная перестановка.количество перестановок данного размера,*<tex>\mathtt{was[1..n] }</tex> {{---}} использовали ли мы уже эту цифру в перестановке.,
'''functionint''' NumOfPermutationFuncpermutation2num(a: '''list <Aint>'''): numOfPermutation = 0 '''for''' i = 1 '''to''' n '''do''' '' <font color=green>// <tex>n </tex> {{--- }} количество элементов в перестановке''</font> '''for''' j = 1 '''to''' a[i] - 1 '''do''' '' <font color=green>// перебираем элементэлементы, лексикографически меньший меньшие нашего, который может которые могут стоять на <tex>i</tex>-м месте </font> '''if''' was[j] == ''false '' <font color=green>// если элемент <tex>j </tex> ранее не был использован</font> '''then''' numOfPermutation += P[n - i] '' <font color=green>// все перестановки с префиксом длиной <tex>i-1 </tex> равным нашему, и <tex>i</tex>-й элемент у которых </font> '' <font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки </font> was[a[i]] = ''true '' <font color=green>// <tex>i</tex>-й элемент использован </font>
'''return''' numOfPermutation
== См. также ==
*[[Получение объекта по номеру|Получение объекта по номеру]]
*[[Получение следующего объекта|Получение следующего объекта]]
*[[Правильные скобочные последовательности#.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|Получение номера правильной скобочной последовательности]]
== Источники информации ==
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]