16
правок
Изменения
→Алгоритм
== Алгоритм ==
'''Нахождение номера по объекту:'''
<tex> n = \sum_{i=1}^l s_{a_i-1}</tex>, где <tex>s_ms_{a_i-1}</tex> это кол-во возможных объектов длины <tex>n-i+1</tex>, начинающихся на элемент <tex>m</tex>, <tex>l</tex> - длина данного объекта.
Возьмем к примеру нахождение номера перестановки. Нам задана произвольная перестановка из N чисел. Пусть x - ее первое число. Тогда все перестановки с первыми числами от 1 до x-1 находятся перед нашей. Их количество num равно (x-1)·(N-1)!. Осталось узнать номер перестановки из N-1 числа, получающейся из нашей выбрасыванием числа x, и прибавить этот номер к num '''Нахождение объекта по номеру:'''
Пусть <tex>l</tex> - длина объекта. Идем по порядку по всем элементам объекта (<tex>i</tex> - позиция элемента в объекте). Каждый элемент <tex>p</tex> будет являться максимально возможным. Для <tex>p</tex> кол-во возможных объектов <tex>s</tex>, начинающихся на элемент <tex>p</tex> и имеющих длину <tex>l-i+1</tex>, не превосходит <tex>n</tex>. С каждым шагом <tex>n</tex> уменьшается на <tex>s</tex>.
Возьмем к примеру нахождение перестановки по номеру. Алгоритм получения перестановки по ее номеру реализуется аналогично: сначала определяем первую цифру перестановки, деля номер на (N-1)! и прибавляя 1, затем вторую, деля остаток от предыдущего деления на (N-2)!, и т.д.
== Примеры ==
