Изменения

Получаем элементы объекта по порядку: сначала определим , какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы нашли первые <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>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Стоит отметить, что подсчет количества комбинаторных объектов с заданным префиксомзачастую является задачей с достаточно большой вычислительной сложностью. Приведем примеры получения некоторых [[Комбинаторные объекты|комбинаторных объектов]] по номеру.

*'''n''' {{--== Битовые вектора ==Рассмотрим алгоритм получения <tex>k</tex>-}} количество мест ого в комбинаторном объекте (например, битовый вектор длины лексикографическом порядке битового вектора размера <tex>n</tex>).При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия:

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

Рассмотрим алгоритм получения <tex>ik</tex>-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера <tex>n</tex>.

*'''<tex>\mathtt{k}</tex> {{---}} номер искомой последовательности,*<tex>\mathtt{n!''' }</tex> {{---}} количество перестановок размера <tex>n</tex>,*'''<tex>\mathtt{permutation[n]''' }</tex> {{---}} искомая перестановка,*'''<tex>\mathtt{was[n]''' }</tex> {{---}} использовали ли мы уже эту цифру в перестановке.

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

== Битовые вектора Сочетания ==Рассмотрим алгоритм получения На каждой итерации мы проверяем, входит ли число <tex>\mathtt{next}</tex> в искомое сочетание. Если мы хотим взять <tex>\mathtt{next}</tex>, то номер сочетания должен быть меньше, чем <texdpi=140>i\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}</tex>, мы пропустили. В обоих случаях рассмотрение текущего числа <tex>next</tex> мы заканчиваем и переходим к следующему числу. Так как у нас всего два возможных элемента*<tex>\mathtt{choose}</tex> {{---}} искомое сочетание, упростим второй цикл до условия:  *'''bitvector<tex>\mathtt{C[n]''' [k]}</tex> {{---}} искомый битовый векторколичество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,

* '''2^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>2^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