http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=217.66.157.54&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T09:59:46ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BF%D0%BE_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83&diff=33371Получение номера по объекту2013-11-02T10:58:34Z<p>217.66.157.54: /* Перестановки */</p>
<hr />
<div>== Описание алгоритма ==<br />
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с 0). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). <br />
Следующий алгоритм вычисляет эту сумму<br />
*numOfObject {{---}} искомый номер комбинаторного объекта.<br />
*a[1..n] {{---}} данный комбинаторный обьект.<br />
*d[i][j] - (количество комбинаторных объектов с префиксом от 1 до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>)<br />
numOfObject = 0 <br />
'''for''' i = 1 '''to''' n '''do''' ''// перебираем элементы комбинаторного объекта''<br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элементы которые в лексикографическом порядке меньше рассматриваемого''<br />
'''if''' элемент j можно поставить на i-e место<br />
'''then''' numOfObject += d[i][j]<br />
Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> - количество различных элементов, которые могут находиться в данном комбинаторном объекте. Для битового вектора <tex>k=2</tex>: возможны только 0 и 1. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. <br />
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.<br />
<br />
== Перестановки ==<br />
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>.<br />
*P[1..n] {{---}} количество перестановок данного размера.<br />
*a[1..n] {{---}} данная перестановка.<br />
*was[1..n] {{---}} использовали ли мы уже эту цифру в перестановке.<br />
<br />
'''for''' i = 1 '''to''' n '''do''' ''// n - количество цифр в перестановке''<br />
'''for''' j = 1 '''to''' a[i] - 1 '''do''' ''// перебираем элемент, который может стоять на i-м месте лексикографически меньше нашего<br />
'''if''' was[j] == false ''// если элемент j ранее не был использован<br />
'''then''' numOfPermutation += P[n - i] ''// все перестановки с префиксом длиной i-1 равным нашему, и i-й элемент у которых меньше <br />
'' нашего в лексикографическом порядке идут раньше данной перестановки <br />
was[i] = true ''// элемент i использован <br />
<br />
Данный алгоритм работает за <tex>O(n ^ 2) </tex>.<br />
<br />
== Битовые вектора ==<br />
Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>.<br />
Количество битовых векторов длины <tex>n</tex> {{---}} <tex>2^n</tex>.<br />
На каждой позиции может стоять один из двух элементов, независимо от того, какие элементы находятся в префиксе, поэтому поиск меньших элементов можно упростить до условия: <br />
*numOfBitvector {{---}} искомый номер вектора.<br />
*bitvector[1..n] {{---}} данный вектор.<br />
'''for''' i = 1 '''to''' n '''do''' <br />
'''if''' bitvector[i] == 1 '''{'''<br />
numOfBitvector += 2 ^ (n - i) <br />
'''}'''<br />
<br />
== См. также ==<br />
*[[Получение объекта по номеру|Получение объекта по номеру]]<br />
<br />
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Комбинаторика]]</div>217.66.157.54