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

2013-11-02T10:58:34Z

217.66.157.54: /* Перестановки */

== Описание алгоритма ==
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с 0). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).
Следующий алгоритм вычисляет эту сумму
*numOfObject {{---}} искомый номер комбинаторного объекта.
*a[1..n] {{---}} данный комбинаторный обьект.
*d[i][j] - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)
numOfObject = 0
'''for''' i = 1 '''to''' n '''do''' ''// перебираем элементы комбинаторного объекта''
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элементы которые в лексикографическом порядке меньше рассматриваемого''
'''if''' элемент j можно поставить на i-e место
'''then''' numOfObject += d[i][j]
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Для битового вектора <tex>k=2</tex>: возможны только 0 и 1. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается.
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.

== Перестановки ==
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.
*P[1..n] {{---}} количество перестановок данного размера.
*a[1..n] {{---}} данная перестановка.
*was[1..n] {{---}} использовали ли мы уже эту цифру в перестановке.

'''for''' i = 1 '''to''' n '''do''' ''// n - количество цифр в перестановке''
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элемент, который может стоять на i-м месте лексикографически меньше нашего
'''if''' was[j] == false ''// если элемент j ранее не был использован
'''then''' numOfPermutation += P[n - i] ''// все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых меньше
'' нашего в лексикографическом порядке идут раньше данной перестановки
was[i] = true ''// элемент i использован

Данный алгоритм работает за <tex>O(n ^ 2) </tex>.

== Битовые вектора ==
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.
Количество битовых векторов длины <tex>n</tex> {{---}} <tex>2^n</tex>.
На каждой позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия:
*numOfBitvector {{---}} искомый номер вектора.
*bitvector[1..n] {{---}} данный вектор.
'''for''' i = 1 '''to''' n '''do'''
'''if''' bitvector[i] == 1 '''{'''
numOfBitvector += 2 ^ (n - i)
'''}'''

== См. также ==
*[[Получение объекта по номеру|Получение объекта по номеру]]

*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Викиконспекты - Вклад участника [ru]

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