29
правок
Изменения
Нет описания правки
== Описание алгоритма ==
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <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>),
'''int''' object2num(a: '''list <A>''') :
numOfObject = 0
'''for''' i = 1 '''to''' n '''do''' <font color=green>// перебираем элементы комбинаторного объекта</font>
'''for''' j = 1 <tex>A_{min}</tex> '''to''' a[i] - 1 предшествующий элемент '''do''' <font color=green>// перебираем элементы, которые в лексикографическом порядке меньше рассматриваемого</font>
'''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место
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>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор,
*<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора,
'''int''' bitvector2num(bitvector: '''list<int>'''):
numOfBitvector = 0
'''for''' i = 1 '''to''' n '''do'''
'''if''' bitvector[i] == 1
numOfBitvector += pow(2, n - i)
'''return''' numOfBitvector
Асимптотика алгоритма {{---}} <tex>O(n) </tex>.
== Перестановки ==
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.,*<tex>P\mathtt{a[1..n]}</tex> {{---}} количество перестановок данного размера.данная перестановка,*<tex>a\mathtt{P[1..n]}</tex> {{---}} данная перестановка.количество перестановок данного размера,*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке.,
'''int''' permutation2num(a: '''list <int>'''):
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>
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
== Сочетания ==
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex>C_n^\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex>$$\sum_{i=1}^{val_1-1} C_\binom{n-i}^{k-1}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex>$$\sum_{i=val_1+1}^{val_2-1} C_\binom{n-i}^{k-2}$$</tex>. Аналогично продолжаем по следующим позициям:*<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания.,*<tex>choose\mathtt{C[n][1..Kk]}</tex> {{---}} данное сочетание, состоящее количество сочетаний из <tex>Kn</tex> чисел от по <tex>1</tex> до <tex>Nk</tex>, из технических соображений припишем ноль в начало сочетания: <tex>choose\mathtt{C[n][0] = 01}</tex>.,*<tex>C\mathtt{choose[n][k1..K]}</tex> {{---}} количество сочетаний данное сочетание, состоящее из <tex>nK</tex> чисел от <tex>1</tex> по до <tex>kN</tex>, из технических соображений припишем ноль в начало сочетания: <tex>C[n]\mathtt{choose[0] = 10}</tex>.,
<font color=green>// Нумерация сочетаний с <tex>0</tex></font>
'''int''' choose2num(choose: '''list <int>'''):
numOfChoose = 0
'''for''' i = 1 '''to''' K '''do'''
Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex>.
== См. также ==
