Изменения

== Описанте Описание алгоритма ==Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>).Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса.Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает , а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте(<tex>i=0..n-1</tex>). Следующий алгоритм вычисляет эту сумму: *<tex>\mathtt{numOfObject = 0 ''}<// 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>,  '''forint''' object2num(a: '''list<A>' i = 1 ''): numOfObject = 0 'to''for' n ''i = 1 'do''to' ''n <font color=green>// перебираем элементы комбинаторного объекта''</font> '''for''' j = 1 '''to''' a[i] - 1 '''do''' '' <font color=green>// перебираем элементы которые , в лексикографическом порядке меньше меньшие рассматриваемого''</font> '''if''' элемент <tex>j </tex> можно поставить на <tex>i</tex>-e место numOfObject += d[i][j] '''thenreturn''' numOfObject += (коллличество комбинаторных объектов с префиксом от 1 до i-1 равным данному и с i-м элементом равным j)т.е. он правильно находит номер данного объекта. Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.

Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановки перестановке размера <tex>n.</tex>, P*<tex>\mathtt{a[1..n] ''}</tex> {{---}} количество перестановок размера nданная перестановка, permutation[*<tex>\mathtt{(n] ''- i)!}</tex> {{---}} данная перестановка''количество перестановок размера <tex>(n - i)</tex>, *<tex>\mathtt{was[1..n] ''}</tex> {{---}} использовали ли мы уже эту цифру в перестановке'' '''for''' i = 1 '''to''' n '''do''' ''// n - количество цифр в перестановке'' '''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элемент который может стоять на i-м месте лексикографически меньше нашего '''if''' was[j] = false ''// если элемент j ранее не был использован '''then ''' numOfPermutation += P[n-i] ''// все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых меньше '' нашего в лексикографическом порядке идут раньше данной престановки was[i] = true ''// элемент i использован

Данный алгоритм работает за '''int''' permutation2num(a: '''list<int>'''): numOfPermutation = 0 '''for''' i = 1 '''to''' n <font color=green>// <tex>On</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^2- 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>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта. == Битовые вектора Сочетания ==Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}</tex> ; число сочетаний, в лексикографическом порядке данного битового вектора размера которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <texdpi=140>\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}</tex>.Аналогично продолжаем по следующим позициям:Колличество битовых векторов длины *<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,*<tex>\mathtt{C[n][k]}</tex> = {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>2^\mathtt{C[n][0] = 1}</tex>,На каждой позиции может стоять один *<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из двух элементов, независимо <tex>K</tex> чисел от того<tex>1</tex> до <tex>N</tex>, какие элементы находятся из технических соображений припишем ноль в префиксеначало сочетания: <tex>\mathtt{choose[0] = 0}</tex>, поэтому поиск меньших элементов можно упростить до условия  '''int''' choose2num(choose: '''list<int>'''): numOfChoose = 0 '''for''' i = 1 '''to''' n K '''for''' j = choose[i - 1] + 1 '''doto''' choose[i] - 1 numOfChoose += C[N - j][K - i] '''ifreturn''' bitvectornumOfChoose Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта. == Разбиение на слагаемые ==Рассмотрим алгоритм получения номера, в лексикографическом порядке, по данному разбиению на слагаемые числа <tex>N</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически, и будем строить его.  *<tex>\mathtt{numOfPart}</tex> {{---}} искомый номер разбиения*<tex>\mathtt{last}</tex> {{---}} последнее поставленное число в разбиении.*<tex>\mathtt{sum}</tex> {{---}} сумма, которую мы уже поставили.*<tex>\mathtt{part[1 \ldots N]}</tex> {{---}} данное разбиение*<tex>\mathtt{d[i][j]}</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые, где каждое слагаемое <tex>\geqslant j</tex>.  Пересчитывать <tex>\mathtt{d[i][j]}</tex> будем по возрастанию <tex>i</tex>, а при равенстве <tex>i</tex> {{---}} по убыванию <tex>j</tex>.  Разбиение числа, в котором каждое слагаемое <tex> \geqslant j</tex> может либо содержать слагаемое <tex>j</tex> (таких разбиений <tex>\mathtt{d[i - j][j]}</tex>), либо не содержать (таких разбиений <tex>\mathtt{d[i] [j + 1]}</tex>).  Получаем рекуррентное соотношение для подсчёта <tex>d</tex>: <p><tex dpi = "145">d[i][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 numOfBitvector '''for''' j = last '''to''' part[i] - 1 <font color=green>// перебираем все элементы, лексикографически меньшие текущего, но не меньшие предыдущего</font> numOfPart += 2 ^ (n 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>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>. Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт.