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