Изменения

== Определение Описание алгоритма ==Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <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 <font color=green>// перебираем элементы комбинаторного объекта</font> '''for''' j = 1 '''to''' a[i] - это нахождение номера объекта1 <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>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.

'''int''' bitvector2num(bitvector: '''list<int>'''): numOfBitvector =0 '''for''' i = Пример 1 '''to''' n '''if''' bitvector[i] ==1 numOfBitvector += <tex>2^{n-i}</tex> '''return''' numOfBitvector

Возьмем перестановки из 3Асимптотика алгоритма {{-х элементов в лексикографическом порядке, найдем номер перестановки 132:--}} <tex>O(n) </tex>.

123,== Перестановки =='''132'''Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,213*<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,231*<tex>\mathtt{(n - i)!}</tex> {{---}} количество перестановок размера <tex>(n - i)</tex>,312*<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,321

Номер искомой '''int''' permutation2num(a: '''list<int>'''): numOfPermutation = 0 '''for''' i = 1 '''to''' n <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> '''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> '''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> numOfPermutation += (n - i)! <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> <font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки: 2.</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> обозначается как <texdpi=140> \binom{n }{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi= 140>\sum\sum_limits^{val_1-1}_{i=1}^l s_{a_i\binom{n-i}{k-1}}</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, где равно <texdpi=140>s_\sum\limits^{a_ival_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}</tex>. Аналогично продолжаем по следующим позициям:*<tex>\mathtt{numOfChoose}</tex> это кол{{---во возможных объектов длины }} искомый номер сочетания,*<tex>\mathtt{C[n][k]}</tex> {{---i+}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>, начинающихся на элемент *<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>mN</tex>, из технических соображений припишем ноль в начало сочетания: <tex>l\mathtt{choose[0] = 0}</tex> - длина данного объекта.,

Нам задана произвольная перестановка из == Разбиение на слагаемые ==Рассмотрим алгоритм получения номера, в лексикографическом порядке, по данному разбиению на слагаемые числа <tex>N чисел</tex>. Пусть x - ее первое числоНужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Тогда все перестановки с первыми числами от 1 до x-1 находятся перед нашей. Их количество num равно (x-1)·(N-1)!. Осталось узнать номер перестановки из N-1 числаИз всех разбиений, получаемых перестановками слагаемых, выберем то, получающейся из нашей выбрасыванием числа xгде слагаемые упорядочены лексикографически, и прибавить этот номер к numбудем строить его.

Возьмем перестановку из 4 чисел: 3124. Перестановки, начинающиеся на Разбиение числа 1, 2 находятся перед нашей. Их количество: 2*в котором каждое слагаемое <tex> \geqslant j</tex> может либо содержать слагаемое <tex>j</tex> (4таких разбиений <tex>\mathtt{d[i -1j][j]}</tex>)!=12. Следовательно минамально возможный номер нашей перестановки: 12+1=13. Следующий элемент перестановки - 1, минимально возможный, следовательно номер перестановки либо не поменялся. 3-ий элемент перестановки - 2, т.к. число содержать (таких разбиений <tex>\mathtt{d[i][j + 1 уже использовалось ранее в перестановке, то число 2 - минимально возможный элемент, и он также не меняет номер перестановки. Последний элемент не играет роли. Следовательно номер нашей перестановки 13]}</tex>).

<p><tex dpi = "145">d[httpi][j] = \left \{\begin{array}{ll} 1, & i = j, \\ 0, & i < j \\ d[i][j + 1] + d[i - j][j], & i > j \end{array} \right. </tex></p>   '''int''' part2num(part:'''list<int>'''): numOfPart = 0, last = 0, sum = 0 '''for''' i = 1 '''to''' part.size '''for''' j = last '''to''' part[i] - 1 <font color=green>//wwwперебираем все элементы, лексикографически меньшие текущего, но не меньшие предыдущего</font> numOfPart += d[N - sum - j][j] <font color=green>// прибавляем количество перестановок, которые могли начинаться с <tex>j</tex></font> sum += part[i] <font color=green>// увеличиваем уже поставленную сумму</font> last = part[i] <font color=green>// обновляем последний поставленный элемент </font> '''return''' numOfPart <font color=green>// возвращаем ответ</font> Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел.chasolimpПоэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>.de Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</practic_info63tex> на предподсчёт.htm  == См. также ==*[[Получение объекта по номеру |Получение объекта по номеру]]*[[Получение следующего объекта|Получение следующего объекта]]*[[Правильные скобочные последовательности#.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.[[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]]