Получение номера по объекту — различия между версиями
Watson (обсуждение | вклад) (→Описанте алгоритма) |
м (rollbackEdits.php mass rollback) |
||
(не показано 106 промежуточных версий 16 участников) | |||
Строка 1: | Строка 1: | ||
− | == | + | == Описание алгоритма == |
− | Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с 0).Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса.Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает , а <tex>i+1</tex> элемент лексикографически меньше <tex>i+1</tex>-го в данном объекте(<tex>i | + | Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>). |
− | Следующий алгоритм вычисляет эту сумму | + | Следующий алгоритм вычисляет эту сумму: |
− | + | *<tex>\mathtt{numOfObject}</tex> {{---}} искомый номер комбинаторного объекта, | |
− | + | *<tex>\mathtt{a[1..n]}</tex> {{---}} данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества <tex>A</tex>, | |
− | + | *<tex>\mathtt{d[i][j]}</tex> {{---}} количество комбинаторных объектов с префиксом от <tex>1</tex> до <tex>i-1</tex> равным данному и с <tex>i</tex>-м элементом равным <tex>j</tex>, | |
− | + | ||
− | + | '''int''' object2num(a: '''list<A>'''): | |
− | + | numOfObject = 0 | |
− | + | '''for''' i = 1 '''to''' n <font color=green>// перебираем элементы комбинаторного объекта</font> | |
− | Сложность алгоритма {{---}} <tex>O(nk) </tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. | + | '''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, в лексикографическом порядке меньшие рассматриваемого</font> |
+ | '''if''' элемент <tex>j</tex> можно поставить на <tex>i</tex>-e место | ||
+ | numOfObject += d[i][j] | ||
+ | '''return''' numOfObject | ||
+ | Сложность алгоритма {{---}} <tex>O(nk) </tex>, где <tex>k</tex> {{---}} количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора <tex>k=2,</tex> поскольку возможны только <tex>0</tex> и <tex>1</tex>. Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. | ||
Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту. | Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту. | ||
+ | |||
+ | == Битовые вектора == | ||
+ | Рассмотрим алгоритм получения номера <tex>i</tex> в лексикографическом порядке данного битового вектора размера <tex>n</tex>. | ||
+ | Всего существует <tex>2^n</tex> битовых векторов длины <tex>n</tex>. | ||
+ | На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство <tex>1</tex>: | ||
+ | *<tex>\mathtt{bitvector[1..n]}</tex> {{---}} данный вектор, | ||
+ | *<tex>\mathtt{numOfBitvector}</tex> {{---}} искомый номер вектора, | ||
+ | |||
+ | '''int''' bitvector2num(bitvector: '''list<int>'''): | ||
+ | numOfBitvector = 0 | ||
+ | '''for''' i = 1 '''to''' n | ||
+ | '''if''' bitvector[i] == 1 | ||
+ | numOfBitvector += <tex>2^{n-i}</tex> | ||
+ | '''return''' numOfBitvector | ||
+ | |||
+ | Асимптотика алгоритма {{---}} <tex>O(n) </tex>. | ||
== Перестановки == | == Перестановки == | ||
− | Рассмотрим алгоритм получения номера в лексикографическом порядке по данной | + | Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>, |
− | + | *<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка, | |
− | + | *<tex>\mathtt{(n - i)!}</tex> {{---}} количество перестановок размера <tex>(n - i)</tex>, | |
− | + | *<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке, | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | '''int''' permutation2num(a: '''list<int>'''): | |
+ | numOfPermutation = 0 | ||
+ | '''for''' i = 1 '''to''' n <font color=green>// <tex>n</tex> {{---}} количество элементов в перестановке</font> | ||
+ | '''for''' j = 1 '''to''' a[i] - 1 <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font> | ||
+ | '''if''' was[j] == ''false'' <font color=green>// если элемент <tex>j</tex> ранее не был использован</font> | ||
+ | numOfPermutation += (n - i)! <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font> | ||
+ | <font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font> | ||
+ | was[a[i]] = ''true'' <font color=green>// <tex>i</tex>-й элемент использован</font> | ||
+ | '''return''' numOfPermutation | ||
− | == | + | Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </tex> для предподсчёта. |
− | Рассмотрим алгоритм получения номера <tex>i</tex> в | + | |
− | + | == Сочетания == | |
− | + | Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex dpi=140>\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}</tex>. Аналогично продолжаем по следующим позициям: | |
− | + | *<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания, | |
− | + | *<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>, | |
− | + | *<tex>\mathtt{choose[1..K]}</tex> {{---}} данное сочетание, состоящее из <tex>K</tex> чисел от <tex>1</tex> до <tex>N</tex>, из технических соображений припишем ноль в начало сочетания: <tex>\mathtt{choose[0] = 0}</tex>, | |
− | + | ||
+ | '''int''' choose2num(choose: '''list<int>'''): | ||
+ | numOfChoose = 0 | ||
+ | '''for''' i = 1 '''to''' K | ||
+ | '''for''' j = choose[i - 1] + 1 '''to''' choose[i] - 1 | ||
+ | numOfChoose += C[N - j][K - i] | ||
+ | '''return''' numOfChoose | ||
+ | |||
+ | Асимптотика алгоритма {{---}} <tex>O(K \cdot N) </tex> и <tex>O(K \cdot N) </tex> для предподсчёта. | ||
+ | |||
+ | == Разбиение на слагаемые == | ||
+ | Рассмотрим алгоритм получения номера, в лексикографическом порядке, по данному разбиению на слагаемые числа <tex>N</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически, и будем строить его. | ||
+ | |||
+ | *<tex>\mathtt{numOfPart}</tex> {{---}} искомый номер разбиения | ||
+ | *<tex>\mathtt{last}</tex> {{---}} последнее поставленное число в разбиении. | ||
+ | *<tex>\mathtt{sum}</tex> {{---}} сумма, которую мы уже поставили. | ||
+ | *<tex>\mathtt{part[1 \ldots N]}</tex> {{---}} данное разбиение | ||
+ | *<tex>\mathtt{d[i][j]}</tex> {{---}} количество разбиений числа <tex>i</tex> на слагаемые, где каждое слагаемое <tex>\geqslant j</tex>. | ||
+ | |||
+ | Пересчитывать <tex>\mathtt{d[i][j]}</tex> будем по возрастанию <tex>i</tex>, а при равенстве <tex>i</tex> {{---}} по убыванию <tex>j</tex>. | ||
+ | |||
+ | Разбиение числа, в котором каждое слагаемое <tex> \geqslant j</tex> может либо содержать слагаемое <tex>j</tex> (таких разбиений <tex>\mathtt{d[i - j][j]}</tex>), либо не содержать (таких разбиений <tex>\mathtt{d[i][j + 1]}</tex>). | ||
+ | |||
+ | Получаем рекуррентное соотношение для подсчёта <tex>d</tex>: | ||
+ | |||
+ | <p> | ||
+ | <tex dpi = "145">d[i][j] = | ||
+ | \left \{\begin{array}{ll} 1, & i = j, \\ 0, & i < j \\ d[i][j + 1] + d[i - j][j], & i > j \end{array} \right. | ||
+ | </tex> | ||
+ | </p> | ||
+ | |||
+ | |||
+ | '''int''' part2num(part: '''list<int>'''): | ||
+ | numOfPart = 0, last = 0, sum = 0 | ||
+ | '''for''' i = 1 '''to''' part.size | ||
+ | '''for''' j = last '''to''' part[i] - 1 <font color=green>// перебираем все элементы, лексикографически меньшие текущего, но не меньшие предыдущего</font> | ||
+ | numOfPart += d[N - sum - j][j] <font color=green>// прибавляем количество перестановок, которые могли начинаться с <tex>j</tex></font> | ||
+ | sum += part[i] <font color=green>// увеличиваем уже поставленную сумму</font> | ||
+ | last = part[i] <font color=green>// обновляем последний поставленный элемент </font> | ||
+ | '''return''' numOfPart <font color=green>// возвращаем ответ</font> | ||
+ | |||
+ | Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>. | ||
+ | |||
+ | Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт. | ||
== См. также == | == См. также == | ||
*[[Получение объекта по номеру|Получение объекта по номеру]] | *[[Получение объекта по номеру|Получение объекта по номеру]] | ||
+ | *[[Получение следующего объекта|Получение следующего объекта]] | ||
+ | *[[Правильные скобочные последовательности#.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.D1.81.D0.BB.D0.B5.D0.B4.D0.BE.D0.B2.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D0.BD.D0.BE.D1.81.D1.82.D0.B8|Получение номера правильной скобочной последовательности]] | ||
+ | == Источники информации == | ||
*Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31 | *Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31 | ||
+ | *Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008. | ||
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Комбинаторика]] | [[Категория: Комбинаторика]] |
Текущая версия на 19:18, 4 сентября 2022
Описание алгоритма
Номер данного комбинаторного объекта равен количеству меньших в лексикографическом порядке комбинаторных объектов (нумерацию ведём с ). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины совпадает, а элемент лексикографически меньше -го в данном объекте ( ). Следующий алгоритм вычисляет эту сумму:
- — искомый номер комбинаторного объекта,
- — данный комбинаторный обьект, состоящий из числовых представлений лексикографически упорядоченных элементов множества ,
- — количество комбинаторных объектов с префиксом от до равным данному и с -м элементом равным ,
int object2num(a: list<A>): numOfObject = 0 for i = 1 to n // перебираем элементы комбинаторного объекта for j = 1 to a[i] - 1 // перебираем элементы, в лексикографическом порядке меньшие рассматриваемого if элементможно поставить на -e место numOfObject += d[i][j] return numOfObject
Сложность алгоритма —
, где — количество различных элементов, которые могут находиться в данном комбинаторном объекте. Например, для битового вектора поскольку возможны только и . Количества комбинаторных объектов с заданными префиксами считаются известными, и их подсчет в сложности не учитывается. Приведем примеры способов получения номеров некоторых из комбинаторных объектов по данному объекту.Битовые вектора
Рассмотрим алгоритм получения номера
в лексикографическом порядке данного битового вектора размера . Всего существует битовых векторов длины . На каждой позиции может стоять один из двух элементов независимо от того, какие элементы находятся в префиксе, поэтому поиск элементов меньше рассматриваемого можно упростить до проверки элемента на равенство :- — данный вектор,
- — искомый номер вектора,
int bitvector2num(bitvector: list<int>):
numOfBitvector = 0
for i = 1 to n
if bitvector[i] == 1
numOfBitvector +=
return numOfBitvector
Асимптотика алгоритма —
.Перестановки
Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера
,- — данная перестановка,
- — количество перестановок размера ,
- — использовали ли мы уже эту цифру в перестановке,
int permutation2num(a: list<int>): numOfPermutation = 0 for i = 1 to n //— количество элементов в перестановке for j = 1 to a[i] - 1 // перебираем элементы, лексикографически меньшие нашего, которые могут стоять на -м месте if was[j] == false // если элемент ранее не был использован numOfPermutation += (n - i)! // все перестановки с префиксом длиной равным нашему, и -й элемент у которых меньше нашего в лексикографическом порядке, идут раньше данной перестановки was[a[i]] = true // -й элемент использован return numOfPermutation
Асимптотика алгоритма —
и для предподсчёта.Сочетания
Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из
по . Как известно, количество сочетаний из по обозначается как . Тогда число сочетаний, в которых на позиции стоит значение , равно ; число сочетаний, в которых на позиции стоит значение , равно . Аналогично продолжаем по следующим позициям:- — искомый номер сочетания,
- — количество сочетаний из по , ,
- — данное сочетание, состоящее из чисел от до , из технических соображений припишем ноль в начало сочетания: ,
int choose2num(choose: list<int>): numOfChoose = 0 for i = 1 to K for j = choose[i - 1] + 1 to choose[i] - 1 numOfChoose += C[N - j][K - i] return numOfChoose
Асимптотика алгоритма —
и для предподсчёта.Разбиение на слагаемые
Рассмотрим алгоритм получения номера, в лексикографическом порядке, по данному разбиению на слагаемые числа
. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически, и будем строить его.- — искомый номер разбиения
- — последнее поставленное число в разбиении.
- — сумма, которую мы уже поставили.
- — данное разбиение
- — количество разбиений числа на слагаемые, где каждое слагаемое .
Пересчитывать
будем по возрастанию , а при равенстве — по убыванию .Разбиение числа, в котором каждое слагаемое
может либо содержать слагаемое (таких разбиений ), либо не содержать (таких разбиений ).Получаем рекуррентное соотношение для подсчёта
:
int part2num(part: list<int>):
numOfPart = 0, last = 0, sum = 0
for i = 1 to part.size
for j = last to part[i] - 1 // перебираем все элементы, лексикографически меньшие текущего, но не меньшие предыдущего
numOfPart += d[N - sum - j][j] // прибавляем количество перестановок, которые могли начинаться с
sum += part[i] // увеличиваем уже поставленную сумму
last = part[i] // обновляем последний поставленный элемент
return numOfPart // возвращаем ответ
Стоит отметить, что количество итераций вложенного цикла не более, чем
, так как всего количество возможных слагаемых — , и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с , которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма — .Асимптотика алгоритма —
и на предподсчёт.См. также
Источники информации
- Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. стр.31
- Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.