== Определение Общий алгоритм получения номера в лексикографическом порядке по комбинаторному объекту ==
Получим элементы объекта по порядку: сначала определим какой элемент будет стоять на 1-м месте, 2-м и т.д. Пусть мы нашли первые i элементов нашего объекта. Для всех вариантов элемента, который может стоять на (i+1)-ой позиции, посчитаем диапазон номеров, который будет сообветствовать объектам с данным префиксом. Если искомый номер входит в один из диапазонов, то, очевидно, мы нашли элемент, который должени стоять на (i+1)-ом месте. (Диапазоны номеров не пересекаются, значит, на это место больше нельзя поставить никакой другой элемент, соответственно, это единственный элемент, который может стоять на этой позиции). '''for''' i = 1 '''to''' n '''do'Получение номера по объекту'' ''//перебираем элементы комбинаторного объекта'' '''for''' j = 1 '''to''' i- это нахождение номера объекта, стоящего 1 '''do''' ''//перебираем элементы которые в лексикографическом порядкеменьше рассматриваемого'' '''if''' элемент j можно поставить на i-e место '''then ans+=(коллличество комбинаторных объектов с данн if Несложно понять, что корректность алгоритма следует из его построения.Сложность алгоритма <tex>O(n^{2}f(1..i)) </tex>, где <tex>f(1..i)</tex> - сложность вычисления количества комбинаторных объектов с данным префиксом. Основную сложность при построении алгоритмов генерации комбинаторных объектов составляет вычисление количества комбинаторных объектов с данным префиксом. Приведем примеры способов нахождения количества некоторых из [[Комбинаторные объекты|комбинаторных объектов]].
== Перестановки ==
Рассмотрим алгоритм получения i-ой в лексикографическом порядке перестановки размера n.
<tex>P_{n} </tex> ''{{---}} количество перестановок размера n
permutation[n] ''{{---}} искомая перестановка''
was[n] ''{{---}} использовали ли мы уже эту цифру в перестановке''
'''for''' i = 1 '''to''' n '''do''' ''//n - количество цифр в перестановке''
alreadyWas = (numOfPermutation-1) div <tex>P_{n-i} </tex> ''// сколько цифр уже полностью заняты перестановками с меньшим номером''
numOfPermutation = ((numOfPermutation-1) mod <tex>P_{n-i} </tex>) + 1
''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята''
'''for''' j = 1 '''to''' n '''do'''
'''if''' was[j] = false
'''then ''' cntFree++
'''if''' cntFree = alreadyWas+1
'''then ''' ans[i] = j
was[j] = true
== Пример ==Данный алгоритм работает за <tex>O(n^2) </tex>. Мы можем посчитать <tex>P_{n} </tex> за <tex>O(n) </tex>. Асимптотику можно улучшить до <tex>O(n log {n}) </tex>, если использовать структуры данных, которые позволяют искать i-ый элемент множества и удалять элемент множества за <tex>O( log {n}) </tex>. Например декартово дерево по неявному ключу.
Возьмем перестановки из 3== Размещения ==Рассмотрим алгоритм получения i-х элементов го в лексикографическом порядкеразмещения <tex> A^k_n </tex> <tex>A^{k}_{n} </tex> ''{{---}} количество размещений из n по k placement[n] ''{{---}} искомое размещение'' was[n] ''{{---}} использовали ли мы уже эту цифру в размещении'' '''for''' i = 1 '''to''' k '''do''' ''//k - количество цифр в размещении'' alreadyWas = (numOfPlacement-1) div <tex> A^{k-i}_{n-i} </tex> ''// сколько цифр уже полностью заняты размещениями с меньшим номером'' numOfPlacement = ((numOfPlacement-1) mod <tex> A^{k-i}_{n-i} </tex>) + 1 ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, найдем номер перестановки 132:которая еще не занята'' '''for''' j = 1 '''to''' n '''do''' '''if''' was[j] = false '''then ''' cntFree++ '''if''' cntFree = alreadyWas+1 '''then ''' ans[i] = j was[j] = trueСложность алгоритма <tex>O(nk) </tex>.
123,'''132''',213,231,312,321 Номер искомой перестановки: 2. == Алгоритм Сочетания == Рассмотрим алгоритм получения i-го в лексикографическом порядке сочетания <tex> n = \sum_{i=1}С^l s_{a_i-1}k_n </tex>, где <tex>s_С^{a_i-1k}_{n}</tex> это кол''{{---}} количество сочетаний из n по k combination[n] ''{{--во возможных объектов длины <tex>-}} искомое сочетание'' was[n] ''{{---}} использовали ли мы уже эту цифру в сочетании'' '''for''' i+= 1< '''to''' k '''do''' ''//k - количество цифр в сочетании'' ''//tex>вычтем те "группы" где, начинающихся на элемент i-цифра меньше искомой'' numOfCombination = ((numOfCombination-1) mod <tex>mA^{k-i}_{n-i} </tex>) + 1 ''//сейчас мы должны поставить ту цифру, которая еще полностью не занята, т.е. alreadyWas+1, которая еще не занята'' '''for''' j = 1 '''to''' n '''do''' '''if''' was[j] = false '''then ''' cntFree++ '''if''' cntFree = alreadyWas+1 '''then ''' ans[i] = j was[j] = trueСложность алгоритма <tex>lO(nk) </tex> - длина данного объекта. == Алгоритм нахождение номера перестановки Битовые вектора == Нам задана произвольная перестановка из N чисел. Пусть x - ее первое число. Тогда все перестановки с первыми числами от 1 до x-1 находятся перед нашей. Их количество num равно (x-1)·(N-1)!. Осталось узнать номер перестановки из N-1 числа, получающейся из нашей выбрасыванием числа x, и прибавить этот номер к num == Пример нахождения номера перестановки Скобочные последовательности == Возьмем перестановку из 4 чисел: 3124. Перестановки, начинающиеся == Разложение на числа 1, 2 находятся перед нашей. Их количество: 2*(4-1)!слагаемые =12. Следовательно минамально возможный номер нашей перестановки: 12+1=13. Следующий элемент перестановки - 1, минимально возможный, следовательно номер перестановки не поменялся. 3-ий элемент перестановки - 2, т.к. число 1 уже использовалось ранее в перестановке, то число 2 - минимально возможный элемент, и он также не меняет номер перестановки. Последний элемент не играет роли. Следовательно номер нашей перестановки 13. == Ссылки См. также == [http://www.chasolimp.de/practic_info63.htm Получение объекта номера по номеру и объекту|Получение номера по объекту]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
