Изменения

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

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

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

== Размещения ==Рассмотрим Данный алгоритм получения i-го в лексикографическом порядке размещения работает за <tex> AO(n^k_n 2)</tex> , так как в случае перестановок <tex>A^{n=k}_{n} </tex> ''{{---}} количество размещений из n по k placement[n] ''. Мы можем посчитать все <tex>\mathtt{{---}} искомое размещение'' was[n] ''{{---!}} использовали ли мы уже эту цифру в размещении'' '''for''' i = 1 '''to''' k '''do''' ''<//k - количество цифр в размещении'' alreadyWas = (numOfPlacement-1) div tex> за <tex> A^{k-i}_{O(n-i} ) </tex> ''// сколько цифр уже полностью заняты размещениями с меньшим номером''. Асимптотику можно улучшить numOfPlacement = ((numOfPlacement-1) mod до <tex> A^{k-i}_O(n \log {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>i</tex>-й элемент множества и удалять элемент Сложность алгоритма множества за <tex>O(nk\log {n}) </tex>.

Рассмотрим алгоритм получения i-го На каждой итерации мы проверяем, входит ли число <tex>\mathtt{next}</tex> в лексикографическом порядке сочетания искомое сочетание. Если мы хотим взять <tex> С^k_n \mathtt{next}</tex> , то номер сочетания должен быть меньше, чем <texdpi=140>С^\binom{kn - 1}_{nk - 1} </tex> ''{{, так как потом надо будет выбрать <tex>k -1</tex> элемент из <tex>n -1</tex> доступных. Если нет, то будем считать, что <tex dpi=140>\binom{n -1}{k - 1} количество </tex> сочетаний из n по k, начинающихся с <tex>\mathtt{next}</tex>, мы пропустили. В обоих случаях рассмотрение текущего числа <tex>next</tex> мы заканчиваем и переходим к следующему числу. combination[n] ''*<tex>\mathtt{choose}</tex> {{---}} искомое сочетание'', was*<tex>\mathtt{C[n] ''[k]}</tex> {{---}} использовали ли мы уже эту цифру в сочетании'' '''for''' i = 1 '''to''' k '''do''' ''/количество сочетаний из <tex>n</tex> по <tex>k - количество цифр в сочетании'' ''<// вычтем те "группы" гдеtex>, i-цифра меньше искомой'' numOfCombination = ((numOfCombination-1) mod <tex> A^{k-i}_\mathtt{C[n-i][0] = 1} </tex>) + 1 , ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята'' '''forlist<int>''' j = 1 num2choose(n, k, m: '''toint''' n ): next = 1 '''dowhile'''k > 0 '''if''' wasm < C[n - 1][jk - 1] choose.push_back(next) k = false k - 1 '''then else''' cntFree++ '''if''' cntFree m -= C[n - 1][k - 1] n = n - 1 next = alreadyWasnext +1 '''then return''' anschooseАсимптотика приведенного алгоритма {{---}} <tex>O(n)</tex>, предподсчет <tex>\mathtt{C[in] = j was[jk] = trueСложность алгоритма }</tex> {{---}} <tex>O(nkn^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