16
правок
Изменения
Новая страница: «== Определение == '''Получение номера по объекту''' - это нахождение номера объекта, стоящего …»
== Определение ==
'''Получение номера по объекту''' - это нахождение номера объекта, стоящего в лексикографическом порядке.
== Пример ==
Возьмем перестановки из 3-х элементов в лексикографическом порядке, найдем номер перестановки 132:
123
'''132'''
213
231
312
321
Номер искомой перестановки: 2.
== Алгоритм ==
<tex> n = \sum_{i=1}^l s_{a_i-1}</tex>, где <tex>s_{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
== Пример нахождения номера перестановки ==
Возьмем перестановку из 4 чисел: 3124. Перестановки, начинающиеся на числа 1, 2 находятся перед нашей. Их количество: 2*(4-1)!=12. Следовательно минамально возможный номер нашей перестановки: 12+1=13. Следующий элемент перестановки - 1, минимально возможный, следовательно номер перестановки не поменялся. 3-ий элемент перестановки - 2, т.к. число 1 уже использовалось ранее в перестановке, то число 2 - минимально возможный элемент, и он также не меняет номер перестановки. Последний элемент не играет роли. Следовательно номер нашей перестановки 13.
== Ссылки ==
[http://www.chasolimp.de/practic_info63.htm Получение объекта по номеру и номера по объекту]
'''Получение номера по объекту''' - это нахождение номера объекта, стоящего в лексикографическом порядке.
== Пример ==
Возьмем перестановки из 3-х элементов в лексикографическом порядке, найдем номер перестановки 132:
123
'''132'''
213
231
312
321
Номер искомой перестановки: 2.
== Алгоритм ==
<tex> n = \sum_{i=1}^l s_{a_i-1}</tex>, где <tex>s_{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
== Пример нахождения номера перестановки ==
Возьмем перестановку из 4 чисел: 3124. Перестановки, начинающиеся на числа 1, 2 находятся перед нашей. Их количество: 2*(4-1)!=12. Следовательно минамально возможный номер нашей перестановки: 12+1=13. Следующий элемент перестановки - 1, минимально возможный, следовательно номер перестановки не поменялся. 3-ий элемент перестановки - 2, т.к. число 1 уже использовалось ранее в перестановке, то число 2 - минимально возможный элемент, и он также не меняет номер перестановки. Последний элемент не играет роли. Следовательно номер нашей перестановки 13.
== Ссылки ==
[http://www.chasolimp.de/practic_info63.htm Получение объекта по номеру и номера по объекту]
