Изменения

== Определение Описание алгоритма ==Получаем элементы объекта по порядку: сначала определим, какой элемент будет стоять на первом месте, потом на втором и так далее. Считаем, что мы нашли первые <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>k</tex>-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера <tex>n</tex>.$$123Заметим,132что всем префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера,213(так как количество всевозможных суффиксов зависит только от длины) то есть можем просто посчитать "количество диапазонов,231,312,321$$которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>Искомая перестановка: 231.

*<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>l</tex> - длина объекта. Идем по порядку по всем элементам объекта O(<tex>in^2)</tex> - позиция элемента , так как в объекте). Каждый элемент случае перестановок <tex>pn=k</tex> будет являться максимально возможным. Для Мы можем посчитать все <tex>p\mathtt{n!}</tex> кол-во возможных объектов за <tex>sO(n) </tex>, начинающихся на элемент . Асимптотику можно улучшить до <tex>pO(n \log {n}) </tex> и имеющих длину , если использовать структуры данных (например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>l-i+1</tex>, не превосходит -й элемент множества и удалять элемент множества за <tex>O( \log {n</tex>. С каждым шагом <tex>n</tex> уменьшается на <tex>s}) </tex>.

== Алгоритм нахождение перестановки Сочетания ==На каждой итерации мы проверяем, входит ли число <tex>\mathtt{next}</tex> в искомое сочетание. Если мы хотим взять <tex>\mathtt{next}</tex>, то номер сочетания должен быть меньше, чем <tex dpi=140>\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> {{---}} искомое сочетание,*<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по номеру =<tex>k</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(Nnext) k = k - 1 '''else''' m -= C[n - 1][k - 1] n = n -1 next = next + 1 '''return''' chooseАсимптотика приведенного алгоритма {{---}} <tex>O(n)! и прибавляя 1</tex>, затем вторую, деля остаток от предыдущего деления на предподсчет <tex>\mathtt{C[n][k]}</tex> {{---}} <tex>O(N-n^2)!, и т.д.</tex>

== Пример нахождения перестановки по номеруСм. также ==*[[Получение номера по объекту|Получение номера по объекту]]Возьмем номер перестановки из 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[[Категория: Дискретная математика и номера по объектуалгоритмы]][[Категория: Комбинаторика]]