Получение номера об объекту и объекта по номеру — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
Строка 5: Строка 5:
  
 
== Алгоритм ==
 
== Алгоритм ==
Нахождение номера по объекту:
+
'''Нахождение номера по объекту:'''
  
<tex> n = \sum_{i=1}^l s_{a_i-1}</tex>, где <tex>s_m</tex> это кол-во возможных объектов длины <tex>n-i+1</tex>, начинающихся на элемент <tex>m</tex>, <tex>l</tex> - длина данного объекта.
+
<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
 +
 
 +
'''Нахождение объекта по номеру:'''
  
 
Пусть <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>.
 
Пусть <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)!, и т.д.
  
 
== Примеры ==
 
== Примеры ==

Версия 23:40, 15 января 2011

Определение

Получение объекта по номеру n- это нахождение объекта, который стоит n-ым в лексикографическом порядке.

Получение номера по объекту - это нахождение номера объекта, стоящего в лексикографическом порядке.

Алгоритм

Нахождение номера по объекту:

[math] n = \sum_{i=1}^l s_{a_i-1}[/math], где [math]s_{a_i-1}[/math] это кол-во возможных объектов длины [math]n-i+1[/math], начинающихся на элемент [math]m[/math], [math]l[/math] - длина данного объекта.

Возьмем к примеру нахождение номера перестановки. Нам задана произвольная перестановка из N чисел. Пусть x - ее первое число. Тогда все перестановки с первыми числами от 1 до x-1 находятся перед нашей. Их количество num равно (x-1)·(N-1)!. Осталось узнать номер перестановки из N-1 числа, получающейся из нашей выбрасыванием числа x, и прибавить этот номер к num

Нахождение объекта по номеру:

Пусть [math]l[/math] - длина объекта. Идем по порядку по всем элементам объекта ([math]i[/math] - позиция элемента в объекте). Каждый элемент [math]p[/math] будет являться максимально возможным. Для [math]p[/math] кол-во возможных объектов [math]s[/math], начинающихся на элемент [math]p[/math] и имеющих длину [math]l-i+1[/math], не превосходит [math]n[/math]. С каждым шагом [math]n[/math] уменьшается на [math]s[/math].

Возьмем к примеру нахождение перестановки по номеру. Алгоритм получения перестановки по ее номеру реализуется аналогично: сначала определяем первую цифру перестановки, деля номер на (N-1)! и прибавляя 1, затем вторую, деля остаток от предыдущего деления на (N-2)!, и т.д.

Примеры

Вычислим по перестановке ее номер. Возьмем перестановку из 4 чисел: 3124. Перестановки, начинающиеся на числа 1, 2 находятся перед нашей. Их количество: 2*(4-1)!=12. Следовательно минамально возможный номер нашей перестановки: 12+1=13. Следующий элемент перестановки - 1, минимально возможный, следовательно номер перестановки не поменялся. 3-ий элемент перестановки - 2, т.к. число 1 уже использовалось ранее в перестановке, то число 2 - минимально возможный элемент, и он также не меняет номер перестановки. Последний элемент не играет роли. Следовательно номер нашей перестановки 13.

Аналогично по номеру получим перестановку. Возьмем номер перестановки из 4 элементов: 13. Определим первую цифру перестановки, разделим нацело номер на (4-1)! и прибавим 1: [math]x_1[/math] = 13 div (3!) + 1 = 3. Остаток от деления: 1. Аналогично найдем 2-й элемент: [math]x_2[/math] = 1 div (2!) + 1 = 1. Остаток от деления: 1. 3-й элемент: [math]x_3[/math] = 1 div (1!)+1 = 1. Но т.к. число 1 уже использовалось в перестановке, возьмем следующий в лексикографическом порядке элемент, не используемый ранее, 2, следовательно [math]x_3[/math] = 2. 4-ый элемент получается исключением [math]x_4[/math] = 4. Получаем перстановку: 3124.

Ссылки

Получение объекта по номеру и номера по объекту