Изменения

== Определение Описание алгоритма ==Получаем элементы объекта по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы нашли первые <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>.При построении битовых векторов можно не проверять условие возможности постановки какого-то объекта на текущее место. На каждый позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе. Так как у нас всего два возможных элемента, упростим второй цикл до условия:

Возьмем перестановки из 3*<tex>\mathtt{bitvector[n]}</tex> {{---}} искомый битовый вектор,*<tex>\mathtt{numOfBitvector}</tex> {{---}} номер искомого вектора среди всех битовых векторов,*<tex>\mathtt{pow(2, n)}</tex> {{---х элементов в лексикографическом порядке}} <tex>2^{n}</tex> количество битовых векторов длины <tex>n</tex>, найдем перестановку под номером 4 '''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>\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>-ом шаге: 231*<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>\mathtt{n!}</tex> за <tex>O(n) </tex>. Асимптотику можно улучшить до <tex>O(n \log {n}) </tex>, если использовать структуры данных (например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i</tex>-й элемент множества и удалять элемент множества за <tex>O( \log {n}) </tex>.

Пусть == Сочетания ==На каждой итерации мы проверяем, входит ли число <tex>l\mathtt{next}</tex> - длина объектав искомое сочетание. Идем по порядку по всем элементам объекта (Если мы хотим взять <tex>\mathtt{next}</tex>, то номер сочетания должен быть меньше, чем <texdpi=140>i\binom{n - 1}{k - 1}</tex> , так как потом надо будет выбрать <tex>k - позиция элемента в объекте). Каждый 1</tex> элемент из <tex>pn - 1</tex> будет являться максимально возможнымдоступных. Для Если нет, то будем считать, что <texdpi=140>p\binom{n - 1}{k - 1}</tex> кол-во возможных объектов сочетаний, начинающихся с <tex>s\mathtt{next}</tex>, начинающихся на элемент мы пропустили. В обоих случаях рассмотрение текущего числа <tex>pnext</tex> мы заканчиваем и имеющих длину переходим к следующему числу. *<tex>l-i+1\mathtt{choose}</tex>{{---}} искомое сочетание, не превосходит *<tex>\mathtt{C[n][k]}</tex>. С каждым шагом {{---}} количество сочетаний из <tex>n</tex> уменьшается на по <tex>sk</tex>., <tex>\mathtt{C[n][0] = 1}</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>

Возьмем к примеру нахождение перестановки по номеру. Сначала определяем первую цифру перестановки, деля номер на (N-1)! и прибавляя 1, затем вторую, деля остаток от предыдущего деления на (N-2)!, и т.д. == Пример нахождения перестановки по номеруСм. также ==*[[Получение номера по объекту|Получение номера по объекту]]Возьмем номер перестановки из 4 элементов: 13*[[Получение_предыдущего_объекта#.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. Определим первую цифру перестановки, разделим нацело номер на (4-1)! и прибавим 1: <tex>x_1</tex> = 13 div (3!) + 1 = 3B5. Остаток от деления: 1D1. Аналогично найдем 2-й элемент: <tex>x_2</tex> = 1 div (2!) + 1 = 182. Остаток от деления: 1D0. 3-й элемент: <tex>x_3</tex> = 1 div (1!)+1 = 1B0. Но тD0.кBD. число 1 уже использовалось в перестановке, возьмем следующий в лексикографическом порядке элемент, не используемый ранее, 2, следовательно <tex>x_3</tex> = 2D0. 4-ый элемент получается исключением <tex>x_4</tex> = 4B8. Получаем перстановку: 3124D1.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|Генерация следующего сочетания]]== Ссылки Источники информации == [http*Программирование в алгоритмах / С. М. Окулов. — М.://wwwБИНОМ.chasolimpЛаборатория знаний, 2002.de/practic_info63стр.htm Получение объекта по номеру 31 - ISBN 5-94774-010-9[[Категория: Дискретная математика и номера по объектуалгоритмы]][[Категория: Комбинаторика]]