Изменения

== Общий алгоритм получения номера Описание алгоритма ==Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке ]] комбинаторных объектов (нумерацию ведём с <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: сначала определим какой элемент будет стоять на 1-м месте, 2-м и т.д. Пусть мы нашли первые i элементов нашего объекта. Для всех вариантов элемента, который может стоять на (i+1'''list<A>''')-ой позиции, посчитаем диапазон номеров, который будет сообветствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должени стоять на (i+1)-ом месте. (Диапазоны номеров не пересекаются, значит, на это место больше нельзя поставить никакой другой элемент, соответственно, это единственный элемент, который может стоять на этой позиции).: 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 место numOfObject += d[i][j] '''then ans+=(коллличество комбинаторных объектов с данн if Несложно понять, что корректность алгоритма следует из его построения.return''' numOfObjectСложность алгоритма {{---}} <tex>O(n^nk) </tex>, где <tex>k</tex> {{2---}}f(1количество различных элементов, которые могут находиться в данном комбинаторном объекте..i)) Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex>, где и <tex>f(1..i)</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>.

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

Данный алгоритм работает за '''int''' permutation2num(a: '''list<texint>O('''): numOfPermutation = 0 '''for''' i = 1 '''to''' n^2) <font color=green>//<tex>. Мы можем посчитать n</tex>P_{n{---}} количество элементов в перестановке</font> '''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex> за -м месте</font> '''if''' was[j] == ''false'' <font color=green>// если элемент <tex>O(n) j</tex>. Асимптотику можно улучшить ранее не был использован</font> до numOfPermutation += P[n - i] <font color=green>// все перестановки с префиксом длиной <tex>O(n log {n}) i-1</tex>равным нашему, если использовать структуры данных, которые позволяют искать и <tex>i</tex>-ый элемент множества и удалять й элемент у которых</font> <font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> множества за was[a[i]] = ''true'' <font color=green>// <tex>O( log {n}) i</tex>. Например декартово дерево по неявному ключу.-й элемент использован</font> '''return''' numOfPermutation

== Размещения ==Рассмотрим алгоритм получения i-го в лексикографическом порядке размещения <tex> A^k_n </tex> <tex>A^Асимптотика алгоритма {k}_{n} </tex> ''{{---}} количество размещений из n по k placement[n] ''{{---}} искомое размещение'' was[n] ''{{---}} использовали ли мы уже эту цифру в размещении'' '''for''' i = 1 '''to''' k '''do''' ''//k - количество цифр в размещении'' alreadyWas = (numOfPlacement-1) div <tex> A^{k-i}_{n-i} </tex> ''// сколько цифр уже полностью заняты размещениями с меньшим номером'' numOfPlacement = O((numOfPlacement-1n ^ 2) mod <tex> A^{k-i}_{n-i} </tex>) + 1 ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята'' '''for''' j = 1 '''to''' n '''do''' '''if''' was[j] = false '''then ''' cntFree++ '''if''' cntFree = alreadyWas+1 '''then ''' ans[i] = j was[j] = trueСложность алгоритма и <tex>O(nkn) </tex>для предподсчёта.

Рассмотрим алгоритм получения i-го номера в лексикографическом порядке данного сочетания из <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>, равно <texdpi=140> С\sum\limits^k_n {val_1-1}_{i=1} {\binom{n-i}{k-1}}</tex> ; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <texdpi=140>С\sum\limits^{kval_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}</tex>. Аналогично продолжаем по следующим позициям:*<tex>\mathtt{numOfChoose} </tex> ''{{---}} количество сочетаний из n по kискомый номер сочетания, combination*<tex>\mathtt{C[n] ''[k]}</tex> {{---}} искомое сочетание''количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>, was*<tex>\mathtt{choose[n1..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''' K '''for''' k j = choose[i - 1] + 1 '''doto''' choose[i] - 1 numOfChoose += C[N - j][K - i] ''//k - количество цифр в сочетании'return' ''numOfChoose Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </ вычтем те "группы" tex> для предподсчёта. == Разбиение на слагаемые ==Рассмотрим алгоритм получения номера, в лексикографическом порядке, по данному разбиению на слагаемые числа <tex>N</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, гдеслагаемые упорядочены лексикографически, iи будем строить его.  *<tex>\mathtt{numOfPart}</tex> {{---}} искомый номер разбиения*<tex>\mathtt{last}</tex> {{---цифра меньше искомой''}} последнее поставленное число в разбиении. numOfCombination = ((numOfCombination*<tex>\mathtt{sum}</tex> {{---}} сумма, которую мы уже поставили.*<tex>\mathtt{part[1) mod \ldots N]}</tex> A^{k{---}} данное разбиение*<tex>\mathtt{d[i][j]}_</tex> {{n---}} количество разбиений числа <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, т.е. alreadyWas& i < j \\ d[i][j +1] + d[i - j][j], которая еще не занята''& i > j \end{array} \right. </tex></p>   '''for''' j = 1 '''toint''' n part2num(part: '''dolist<int>'''): numOfPart = 0, last = 0, sum = 0 '''iffor''' was[j] i = false 1 '''then to''' cntFree++ part.size '''iffor''' cntFree j = alreadyWas+1 last '''then to''' anspart[i] - 1 <font color= green>// перебираем все элементы, лексикографически меньшие текущего, но не меньшие предыдущего</font> numOfPart += d[N - sum - j][j] <font color=green>// прибавляем количество перестановок, которые могли начинаться с <tex>j </tex></font> sum += part[i] was<font color=green>// увеличиваем уже поставленную сумму</font> last = part[ji] <font color=green>// обновляем последний поставленный элемент </font> '''return''' numOfPart <font color= truegreen>// возвращаем ответ</font>Сложность Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(nkN) </tex>.== Битовые вектора ==== Скобочные последовательности ==Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт.== Разложение на слагаемые ==

*[[Получение номера объекта по номеру|Получение объекта по объектуномеру]]*[[Получение следующего объекта|Получение следующего объекта]]*[[Правильные скобочные последовательности#.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.