Изменения

== Общий алгоритм получения комбинаторного объекта по номеру в лексикографическом порядке Описание алгоритма == В начале каждого шага numOfObject - номер комбинаторного Получаем элементы объекта среди объектов с заданным префиксомпо порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. '''for''' Считаем, что мы нашли первые <tex>i = 1 '''to''' n '''do''' ''<//n - количество tex> элементов в комбинаторном объекте'' '''for''' j = объекта. Для всех вариантов элемента, который может стоять на позиции с номером <tex>i+1 '''to''' n '''do''' ''<//перебираем елементы в лексикографическом порядке'' '''if''' можем поставить на это место '''then if''' numOfObject tex> (количество комбинаторных обектов , посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом)''' '''then''' numOfObject -= (количество комбинаторных обектов . Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должен стоять на месте с данным префиксом) '''else''' '''then''' ans[номером <tex>i]=j ''+1<//поставим tex>. Диапазоны номеров не пересекаются, значит на это место текущий больше нельзя поставить никакой другой элемент, т.к. еще не все объекты с этим префиксом - меньше'' перейти к выбору следующего элемента:

Рассмотрим почему данный алгоритм корректен. Докажем по индукции*в начале каждого шага <tex>\mathtt{numOfObject}</tex> {{---}} номер нужного объекта среди тех, что мы верно выберем первые у которых префикс до <tex>i</tex>-элементов го элемента лексикографически равен префиксу нашего объекта.,*<tex>\mathtt{n}</tex> {{---}} количество мест в комбинаторном объекте (например, битовый вектор длины <tex>n</tex>),Условимся*<tex>\mathtt{k}</tex> {{---}} количество различных элементов, что нумерация обектов начинается с 1которые могут находиться в данном комбинаторном объекте. : База: iНапример, для битового вектора <tex>k=2</tex>, поскольку возможны только <tex>0 - очевидно: </tex> и <tex>1</tex>. ДокажемВсе элементы занумерованы в лексикографическом порядке, что если первые i-элементов выбраны верно, то i+начиная с <tex>1 мы также выберем верно </tex>.Комбинаторные объекты занумерованы с <tex>0</tex>. Переход к нумерации с единицы можно сделать с помощью одной операции декремента перед проходом алгоритма: Переход'''function''' num2object(numOfObject: '''int'''): На '''for''' i+= 1 '''to''' n '''for''' j = 1'''to''' k '''if''' j-ом шаге мы найдем, какой й элемент должен быть можно поставить на i+-e место '''if''' numOfObject >= (количество комбинаторных объектов с префиксом object[1..i-1] и элементом j на месте i) numOfObject -ым для объекта = (количество комбинаторных объектов с номером numOfOject, среди всех комбинаторных обектов, которые имеют префикс длины префиксом object[1..i - как у нас. 1] и элементом j на месте i) '''else''' object[i] = j break '''return''' objectСложность алгоритма {{---}} <tex>O(nk) <br/tex> Рассмотрим искомый объект. ОчевидноКоличества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что все подсчет количества комбинаторных объектов с заданным префиксом зачастую является задачей с достаточно большой вычислительной сложностью. Приведем примеры получения некоторых [[Комбинаторные объекты, у которых символ на |комбинаторных объектов]] по номеру. == Битовые вектора ==i+1 месте меньше чем у нас Рассмотрим алгоритм получения <tex>k</tex>-ого в лексикографическом порядке, будут идти раньше нас (префикс совпадает, а i+1 символ меньше), тбитового вектора размера <tex>n</tex>.еПри построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. наш номерНа каждый позиции может стоять один из двух элементов, по крайней мере большенезависимо от того, количества таких объектовкакие элементы находятся в префиксе. А те Так как у которых больше будут идти после насвсего два возможных элемента, т.е. даже номер найменьшего из них будет больше нашего. Тогда упростим второй цикл до условия:  *<tex>\mathtt{bitvector[n]}<br/tex>{{---}} искомый битовый вектор,(суммы *<tex>\mathtt{numOfBitvector}</tex> {{---}} номер искомого вектора среди всех комбинаторных объектов с "битовых векторов,*<tex>=" префиксом\mathtt{pow(2, n) }</tex>= numOfObject {{---}} <tex>2^{n}</tex> (суммы всех комбинаторных объектов с меньшим "количество битовых векторов длины <" префиксом) tex>n<br/tex> ,т.е. в итоге из построения алгоритма мы поставим именно тот элемент, который нам нужен. '''vector<brint> Далее продолжим искать среди объектов''' num2bitvector(numOfBitvector: '''int'''): '''for''' i = 1 '''to''' n '''if''' numOfBitvector >= pow(2, (n - i)) numOfBitvector -= pow(2, которые имеют одинаковый префикс длины (n - i)) bitvector[i+] = 1 '''else''' bitvector[i] = 0 '''return''' bitvector Данный алгоритм работает за <tex>O(n)</tex>, изменив номер на номер среди комбинаторных объектов с текущим префиксом. так как в случае битовых векторов <tex>k</tex> не зависит от <tex>n<br/tex>. Очевидно, это тоже самое, что искать старый номер, среди старых префиксовАлгоритм эквивалентен переводу числа из десятичной системы в двоичную.

Рассмотрим алгоритм получения i<tex>k</tex>-ой в [[Лексикографический порядок|лексикографическом порядке ]] перестановки размера <tex>n</tex>. Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество всевозможных суффиксов зависит только от длины) то есть можем просто посчитать "количество диапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>: *<tex>P_\mathtt{k}</tex> {{---}} номер искомой последовательности,*<tex>\mathtt{n!} </tex> ''{{--- }} количество перестановок размера <tex>n</tex>, *<tex>\mathtt{permutation[n] ''}</tex> {{--- }} искомая перестановка'', *<tex>\mathtt{was[n] ''}</tex> {{--- }} использовали ли мы уже эту цифру в перестановке''. '''for''' На <tex>i = 1 '''to''' n '''do''' ''<//n tex>- количество цифр в перестановке''ом шаге: alreadyWas = (numOfPermutation-1) div *<tex>P_\mathtt{n-ialreadyWas} </tex> ''// {{---}} сколько цифр уже полностью заняты перестановками с меньшим номером'' numOfPermutation = ((numOfPermutation-1) mod <tex>P_{n-i} </tex>) + 1 , ''//сейчас *мы должны поставить ту цифру, которая еще полностью не занята, т.е. то есть цифру с номером <tex>alreadyWas+1</tex>. Среди цифр, которая которых еще не занятанет в нашем префиксе, считаем, что это цифра <tex>j</tex>.На <tex>j</tex>-ом шаге:*<tex>\mathtt{curFree}</tex> {{---}} если элемент с номером <tex>j</tex> свободен, то он имеет номер curFree среди всех свободных элементов с <tex>1</tex> по <tex>j</tex>. '''list<int>''' num2permutation(k: '''int'''): '''for''' j i = 1 '''to''' n alreadyWas = k / (n - i)! k %= (n - i)! curFree = 0 '''for''' j = 1 '''doto'''n '''if''' was[j] = false = ''false'then ''' cntFree curFree++ '''if''' cntFree curFree == alreadyWas+1 '''then ''' ans permutation[i] = j was[j] = true '''return''' permutation

Данный алгоритм работает за <tex>O(n^2) </tex>, так как в случае перестановок <tex>n=k</tex>. Мы можем посчитать все <tex>P_\mathtt{n!} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить до <tex>O(n \log {n}) </tex>, если использовать структуры данных(например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i</tex>-ый й элемент множества и удалять элемент множества за <tex>O( \log {n}) </tex>. Например декартово дерево по неявному ключу.

Рассмотрим алгоритм получения i-го На каждой итерации мы проверяем, входит ли число <tex>\mathtt{next}</tex> в лексикографическом порядке размещения искомое сочетание. Если мы хотим взять <tex> A^k_n \mathtt{next}</tex> , то номер сочетания должен быть меньше, чем <texdpi=140>A^\binom{kn - 1}_{nk - 1} </tex> '', так как потом надо будет выбрать <tex>k - количество размещений 1</tex> элемент из <tex>n по k placement[n] ''- искомое размещение'' was[n] ''- использовали ли мы уже эту цифру в размещении'' '''for''' i = 1 '''to''' k '''do''' ''<//k - количество цифр в размещении'' alreadyWas = (numOfPlacement-1) div tex> доступных. Если нет, то будем считать, что <texdpi=140> A^\binom{kn -i1}_{nk -i1} </tex> ''сочетаний, начинающихся с <tex>\mathtt{next}</tex>, мы пропустили. В обоих случаях рассмотрение текущего числа <tex>next</ сколько цифр уже полностью заняты размещениями с меньшим номером''tex> мы заканчиваем и переходим к следующему числу. numOfPlacement = ((numOfPlacement*<tex>\mathtt{choose}</tex> {{---1) mod }} искомое сочетание,*<tex> A^\mathtt{C[n][k-i]}_</tex> {n{---i} } количество сочетаний из <tex>n</tex>) + 1 ''по <tex>k<//сейчас мы должны поставить ту цифруtex>, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята'' '''for''' j = 1 '''to''' <tex>\mathtt{C[n '''do''' '''if''' was][j0] = false '''then ''' cntFree++ '''if''' cntFree = alreadyWas+1 '''then ''' ans[i] = j was[j] = trueСложность алгоритма <tex>O(nk) }</tex>.,

'''list<int>''' num2choose(n, k, m: '''int'''): next =1 '''while''' k > 0 '''if''' m < C[n - 1][k - 1] choose.push_back(next) k = Размещения k - 1 '''else''' m -=C[n - 1][k - 1] n =n - 1 next == Битовые вектора ==next + 1 '''return''' chooseАсимптотика приведенного алгоритма {{---}} <tex>O(n)</tex>, предподсчет <tex>\mathtt{C[n][k]}</tex> {{---}} <tex>O(n^2)</tex> == Скобочные последовательности См. также ==*[[Получение номера по объекту|Получение номера по объекту]]*[[Получение_предыдущего_объекта#.D0.A1.D0.BF.D0.B5.D1.86.D0.B8.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D1.8F_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B0_.D0.B4.D0.BB.D1.8F_.D0.B3.D0.B5.D0.BD.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8_.D0.BF.D1.80.D0.B5.D0.B4.D1.8B.D0.B4.D1.83.D1.89.D0.B5.D0.B3.D0.BE_.D1.81.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D1.8F|Получение предыдущего сочетания]]*[[Получение_следующего_объекта#.D0.A1.D0.BF.D0.B5.D1.86.D0.B8.D0.B0.D0.BB.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D1.8F_.D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B0_.D0.B4.D0.BB.D1.8F_.D0.B3.D0.B5.D0.BD.D0.B5.D1.80.D0.B0.D1.86.D0.B8.D0.B8_.D1.81.D0.BB.D0.B5.D0.B4.D1.83.D1.8E.D1.89.D0.B5.D0.B3.D0.BE_.D1.81.D0.BE.D1.87.D0.B5.D1.82.D0.B0.D0.BD.D0.B8.D1.8F|Генерация следующего сочетания]]== Разложение на слагаемые Источники информации ==*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31 - ISBN 5-94774-010-9[[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]]