Изменения

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

Рассмотрим алгоритм получения <tex>ik</tex>-ой в [[Лексикографический порядок|лексикографическом порядке]] перестановки размера <tex>n</tex>.Заметим, что всем префиксом префиксам на каждом шаге будет соответствовать диапазон номеров одинакового размера, (так как количество перестановок не всевозможных суффиксов зависит только от префиксадлины) то есть можем просто посчитать "количество диапозоновдиапазонов, которые идут до нас" (количество цифр уже полностью занятых перестановками с меньшим номером) за <tex>O(1) </tex>:

*'''f[<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>\mathtt{n!}</tex> за <tex>O(n) </tex>. Асимптотику можно улучшить до <tex>O(n \log {n}) </tex>, если использовать структуры данных (например, [[Декартово дерево|декартово дерево]] по неявному ключу), которые позволяют искать <tex>i</tex>-ом шаге:й элемент множества и удалять элемент множества за <tex>O( \log {n}) </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> {{---}} искомое сочетание,*'''alreadyWas''' <tex>\mathtt{C[n][k]}</tex> {{---}} сколько цифр уже полностью заняты перестановками с меньшим номеромколичество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,

*мы должны поставить ту цифру, которая еще полностью не занята, то есть цифру с номером '''alreadyWaslist<int>''' + 1 среди цифрnum2choose(n, которых еще нет в нашем префиксеk, считаем, что это цифра m: '''jint'''): '''for''' i next = 1 '''towhile''' n k > 0 '''doif''' m < C[n - 1][k - 1] choose.push_back(next) k = k - 1 '''{else''' alreadyWas m -= (numOfPermutation C[n - 1) div f][nk -i1] numOfPermutation n = ((numOfPermutation - 1) mod f[n-i]) + 1 ans[i] next = j (посчитаем за O(n))next + 1 теперь j-ый элемент занят (находится в нашем префиксе) '''}return'''chooseДанный алгоритм работает за Асимптотика приведенного алгоритма {{---}} <tex>O(n^2)</tex>, так как в случае перестановок предподсчет <tex>\mathtt{C[n=][k</tex>. Мы можем посчитать все '''f[n]''' за <tex>O(n) }</tex>. Асимптотику можно улучшить до <tex>O(n \log {{n---}}) </tex>, если использовать структуры данных, которые позволяют искать <tex>i</tex>-ый элемент множества и удалять элемент множества за <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