Изменения

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

Рассмотрим алгоритм получения 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>n</tex>,*<tex>\mathtt{permutation[n]}</tex> {{---}} искомая перестановка,*<tex>\mathtt{was[n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке.На <tex>i</tex>-ом шаге:*<tex>\mathtt{alreadyWas}</tex> {{---}} сколько цифр уже полностью заняты перестановками с меньшим номером,*мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером <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''' 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 Данный алгоритм работает за <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{n - 1}{k- 1}_{</tex>, так как потом надо будет выбрать <tex>k - 1</tex> элемент из <tex>n} - 1</tex> ''доступных. Если нет, то будем считать, что <tex dpi=140>\binom{n - 1}{k ---1}</tex> сочетаний, начинающихся с <tex>\mathtt{next} количество размещений из n по k</tex>, мы пропустили. В обоих случаях рассмотрение текущего числа <tex>next</tex> мы заканчиваем и переходим к следующему числу. placement[n] ''*<tex>\mathtt{choose}</tex> {{---}} искомое размещение''сочетание, was*<tex>\mathtt{C[n] ''[k]}</tex> {{---}} использовали ли мы уже эту цифру в размещении'' '''for''' i = 1 '''to''' k '''do''' ''//k - количество цифр в размещении'' alreadyWas = (numOfPlacement-1) div сочетаний из <tex> A^{k-i}_{n-i} </tex> ''// сколько цифр уже полностью заняты размещениями с меньшим номером'' numOfPlacement = ((numOfPlacement-1) mod по <tex> A^{k-i}_{n-i} </tex>) + 1 ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. 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[[Категория: Дискретная математика и алгоритмы]][[Категория: Комбинаторика]]