Изменения

Получим Получаем элементы объекта по порядку: сначала определим , какой элемент будет стоять на 1-м первом месте, 2-м потом на втором и ттак далее.д. Пусть Считаем, что мы нашли первые <tex>i </tex> элементов нашего объекта. Для всех вариантов элемента, который может стоять на (позиции с номером <tex>i+1)-ой позиции</tex>, посчитаем диапазон номеров, который будет соответствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должени должен стоять на (месте с номером <tex>i+1)-ом месте</tex>. (Диапазоны номеров не пересекаются, значит, на это место больше нельзя поставить никакой другой элемент, соответственно, это единственный элемент, который может стоять на этой позиции).:

''В *в начале каждого шага <tex>\mathtt{numOfObject }</tex> {{---}} номер комбинаторного нужного объекта среди тех, у которых префикс до <tex>i</tex>-го элемента лексикографически равен префиксу нашего объекта,*<tex>\mathtt{n}</tex> {{---}} количество мест в комбинаторном объекте (например, битовый вектор длины <tex>n</tex>),*<tex>\mathtt{k}</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2</tex>, поскольку возможны только <tex>0</tex> и <tex>1</tex>. Все элементы занумерованы в лексикографическом порядке, начиная с <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 -= (количество комбинаторных объектов с заданным префиксом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>. Алгоритм эквивалентен переводу числа из десятичной системы в двоичную. == Перестановки ==Рассмотрим алгоритм получения <tex>k</tex>-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера <tex>n</tex>.Заметим, что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество всевозможных суффиксов зависит только от длины) то есть можем просто посчитать "количество диапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:

''*<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 =2 : возможны только 0 и '''for''' j = 1)'''to''' n '''if''' was[j] == ''false'' curFree++ '''if''' curFree == alreadyWas + 1 permutation[i] = j was[j] = true '''return''' permutation

'''for''' i = 1 '''to''' Данный алгоритм работает за <tex>O(n^2)</tex>, так как в случае перестановок <tex>n '''do''' '''for''' j = 1 '''to''' k '''do''' '''if''' элемент j можно поставить на i-e место '''then if''' numOfObject </tex>. Мы можем посчитать все <tex>\mathtt{n!}</tex> за <tex> O(количество комбинаторных обектов с данным префиксомn)''' '''then''' numOfObject -= (количество комбинаторных обектов с данным префиксом) '''else''' '''then''' ans[i]=j перейти к выбору следующего элементаНесложно понять, что корректность алгоритма следует из его построения</tex>.Асимптотику можно улучшить Сложность алгоритма до <tex>O(n^\log {2n}f) </tex>, если использовать структуры данных (1..например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i)) </tex>, где -й элемент множества и удалять элемент множества за <tex>fO(1..i\log {n})</tex> - сложность вычисления количества комбинаторных объектов с данным префиксом. Основную сложность при построении алгоритмов генерации комбинаторных объектов составляет вычисление количества комбинаторных объектов с данным префиксом. Приведем примеры способов получения некоторых из [[Комбинаторные объекты|комбинаторных объектов]] по номеру.

== Перестановки Сочетания ==Рассмотрим алгоритм получения i-ой На каждой итерации мы проверяем, входит ли число <tex>\mathtt{next}</tex> в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера nискомое сочетание.ЗаметимЕсли мы хотим взять <tex>\mathtt{next}</tex>, что всем префиксом на каждом шаге будет соответствовать диапазон номеров одинакового размерато номер сочетания должен быть меньше, (т.к. количество перестановок не зависит от префикса) т.е. можем просто посчитать "количество диапозоновчем <tex dpi=140>\binom{n - 1}{k - 1}</tex>, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за так как потом надо будет выбрать <tex>O(k - 1) </tex>: элемент из <tex>P_{n} - 1</tex> ''доступных. Если нет, то будем считать, что <tex dpi=140>\binom{n - 1}{k ---1}</tex> сочетаний, начинающихся с <tex>\mathtt{next} количество перестановок размера n</tex>, мы пропустили. В обоих случаях рассмотрение текущего числа <tex>next</tex> мы заканчиваем и переходим к следующему числу. permutation[n] ''*<tex>\mathtt{choose}</tex> {{---}} искомая перестановка''искомое сочетание, was*<tex>\mathtt{C[n] ''[k]}</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} k</tex>) + 1 ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1 - ую, которой еще нет в нашем префиксе, пусть это цифра j'' ans[i] = j (посчитаем за <tex>O(\mathtt{C[n) ][0] = 1}</tex>) теперь j-ый элемент занят (находится в нашем префиксе),

Данный алгоритм работает за '''list<texint>O''' num2choose(n^2, k, m: '''int''') : next = 1 '''while''' k > 0 '''if''' m </tex>C[n - 1][k - 1] choose. Мы можем посчитать все <tex>P_push_back(next) k = k - 1 '''else''' m -= C[n - 1][k - 1] n = n - 1 next = next + 1 '''return''' chooseАсимптотика приведенного алгоритма {{n---}} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить до , предподсчет <tex>O(n \log mathtt{C[n][k]}) </tex>, если использовать структуры данных, которые позволяют искать i {{---ый элемент множества и удалять элемент множества за }} <tex>O( \log {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