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

Получение следующего объекта

2022-01-03T20:27:48Z

Npanuhin: Code style

== Алгоритм ==
{{Определение|definition= '''Получение следующего объекта''' {{---}} это нахождение объекта, следующего за данным в [[Лексикографический порядок|лексикографическом порядке]].
}}
Объект <tex>Q</tex> называется следующим за <tex>P</tex>, если <tex>P < Q</tex> и не найдется такого <tex>R</tex>, что <tex>P < R < Q</tex>.

Отсюда понятен алгоритм:
* находим суффикс минимальной длины, который можно изменить без изменения префикса текущего объекта <tex>P</tex>,
* к оставшейся части дописываем минимальный возможный элемент (чтобы было выполнено правило <tex>P < Q</tex>),
* дописываем минимальный возможный хвост.
По построению получаем, что <tex>Q</tex> {{---}} минимально возможный.

== Специализация алгоритма для генерации следующего битового вектора ==
* Находим минимальный суффикс, в котором есть <tex>0</tex>, его можно увеличить, не меняя оставшейся части
* Вместо <tex>0</tex> записываем <tex>1</tex>
* Дописываем минимально возможный хвост из нулей
'''int[]''' nextVector('''int[]''' a): // <tex>n</tex> {{---}} длина вектора
'''while''' (n >= 0) '''and''' (a[n] != 0)
a[n] = 0
n--
'''if''' n == -1
'''return''' ''null''
a[n] = 1
'''return''' a
Приведённый алгоритм эквивалентен прибавлению единицы к битовому вектору.
=== Пример работы ===
{| class="wikitable" border = 1
|0||1||0||1||style="background:#FFCC00"|1||исходный битовый вектор
|-
| || || || ||^|| начинаем идти с конца
|-
|0||1||0||style="background:#FFCC00"|0||style="background:#FFCC00"|0|| пока элементы равны 1, заменяем их на 0
|-
|0||1||style="background:#FFCC00"|1||0||0|| меняем первый не удовлетворяющий условию цикла элемент на 1
|-
|'''0'''||'''1'''||'''1'''||'''0'''||'''0'''||следующий битовый вектор
|}

== Специализация алгоритма для генерации следующей перестановки ==
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример)
* Меняем его с минимальным элементом, большим нашего, стоящим правее
* Перевернем правую часть

'''int[]''' nextPermutation('''int[]''' a): // <tex>n</tex> {{---}} длина перестановки
'''for''' i = n - 2 '''downto''' 0
'''if''' a[i] < a[i + 1]
min = i + 1;
'''for''' j = i + 1 '''to''' n - 1
'''if''' (a[j] < a[min]) '''and''' (a[j] > a[i])
min = j
swap(a[i], a[min])
reverse(a, i + 1, n - 1)
'''return''' a
'''return''' ''null''

=== Пример работы ===
{| class="wikitable" border = 1
|1||3||style="background:#FFCC00"|2||5||style="background:#FFCC00"|4||исходная перестановка
|-
| || ||^|| || ||находим элемент, нарушающий убывающую последовательность
|-
| || || || ||^||минимальный элемент больше нашего
|-
|1||3||style="background:#FFCC00"|4||5||style="background:#FFCC00"|2||меняем их местами
|-
|1||3||4||style="background:#FFCC00"|2||style="background:#FFCC00"|5||разворачивам правую часть
|-
|'''1'''||'''3'''||'''4'''||'''2'''||'''5'''||следующая перестановка
|}

== Специализация алгоритма для генерации следующей мультиперестановки ==
* Двигаясь справа налево, находим элемент, нарушающий убывающую последовательность (в обычном порядке, слева направо, см. пример).
* Меняем его с минимальным элементом, большим нашего, стоящим правее.
* Переворачиваем правую часть.
'''int[]''' nextMultiperm('''int[]''' b): // <tex>n</tex> {{---}} длина мультиперестановки
i = n - 2
'''while''' (i >= 0) '''and''' (b[i] >= b[i + 1])
i--
'''if''' i >= 0
j = i + 1
'''while''' (j < n - 1) '''and''' (b[j + 1] > b[i])
j++
swap(b[i] , b[j])
reverse(b, i + 1, n - 1)
'''return''' b
'''else'''
'''return''' ''null''

=== Пример работы ===
{| class="wikitable" border = 1
|1||2||3||1||style="background:#FFCC00"|2||style="background:#FFCC00"|3||Исходная перестановка.
|-
| || || || ||^|| ||Находим элемент, нарушающий убывающую последовательность.
|-
| || || || || ||^||Минимальный элемент больше нашего.
|-
|1||2||3||1||style="background:#FFCC00"|3||style="background:#FFCC00"|2||Меняем их местами.
|-
|'''1'''||'''2'''||'''3'''||'''1'''||'''3'''||'''2'''||Следующая мультиперестановка.
|}

== Специализация алгоритма для генерации следующего сочетания ==

* Добавим в конец массива с сочетанием <tex>N+1</tex> – максимальный элемент.
* Пойдём справа налево. Будем искать номер элемента, который отличается от предыдущего на <tex>2</tex> и больше.
* Увеличим найденный элемент на <tex>1</tex>, и допишем в конец минимально возможный хвост, если такого элемента нет – на вход было дано последнее сочетание.
'''int[]''' nextChoose('''int[]''' a, '''int''' n, '''int''' k): // <tex>n,k </tex> {{---}} параметры сочетания
'''for''' i = 0 '''to''' k - 1
b[i] = a[i]
b[k] = n + 1
i = k - 1
'''while''' (i >= 0) '''and''' (b[i + 1] - b[i] < 2)
i--
'''if''' i >= 0
b[i]++
'''for''' j = i + 1 '''to''' k - 1
b[j] = b[j - 1] + 1
'''for''' i = 0 '''to''' k - 1
a[i] = b[i]
'''return''' a
'''else'''
'''return''' ''null''

=== Пример работы ===
{| class="wikitable" border = 1
|1||2||5||6||style="background:#FFCC00"|'''7'''||Дописываем 7 в конец сочетания.
|-
|1||style="background:#FFCC00"|2||5||6||'''7'''||
|-
| ||^|| || || ||Находим элемент i, a[i + 1] - a[ i ] >= 2
|-
|1||style="background:#FFCC00"|3||5||6||'''7'''||Увеличиваем его на 1.
|-
|1||3||style="background:#FFCC00"|4||style="background:#FFCC00"|5||style="background:#FFCC00"|'''6'''||Дописываем минимальный хвост.
|-
|'''1'''||'''3'''||'''4'''||'''5'''||''' '''||Следующее сочетание.
|}

== Специализация алгоритма для генерации следующего разбиения на слагаемые ==
Рассматриваемый алгоритм находит следующее [[комбинаторные объекты|разбиение на слагаемые]], при этом разбиение упорядоченно по возрастанию.
* Увеличим предпоследнее слагаемое на <tex>1</tex>, уменьшим последнее слагаемое на <tex>1</tex>.
** Если предпоследнее слагаемое стало больше последнего, то увеличиваем предпоследнее слагаемое на величину последнего.
** Если предпоследнее слагаемое умноженное на 2 меньше последнего, то разбиваем последнее слагаемое <tex>s</tex> на два слагаемых <tex>a</tex> и <tex>b</tex> таких, что <tex>a</tex> равно предпоследнему слагаемому, а <tex>b = s - a</tex>. Повторяем этот процесс, пока разбиение остается корректным, то есть предпоследнее слагаемое хотя бы в два раза меньше последнего.

<code>
// <tex>b</tex> {{---}} список, содержащий разбиение данного числа <tex>b.size</tex>{{---}} его размер 
'''list<int>''' nextPartition('''list<int>''' b):
b[b.size - 1]--
b[b.size - 2]++
'''if''' b[b.size - 2] > b[b.size - 1]
b[b.size - 2] += b[b.size - 1]
b.remove(b.size - 1)
'''else'''
'''while''' b[b.size - 2] * 2 <= b[b.size - 1]
b.add(b[b.size - 1] - b[b.size - 2])
b[b.size - 2] = b[b.size - 3]
'''return''' b
</code>

=== Пример работы ===
{| class="wikitable" border = 1
|1||style="background:#FFCC00"|1||style="background:#FFCC00"|7|| || ||Прибавим 1 + 1, вычтем 7 - 1.
|-
|1||style="background:#FFCC00"|2||style="background:#FFCC00"|6|| || ||Проверяем: 2 < 6, значит разбиваем 6 пока оно не станет меньше 4
|-
|1||2||style="background:#FFCC00"|2||style="background:#FFCC00"|4|| ||
|-
|1||2||2||style="background:#FFCC00"|2||style="background:#FFCC00"|2||
|-
|'''1'''||'''2'''||'''2'''||'''2'''||'''2'''||Следующее разбиение на слагаемые числа 9.
|}

{| class="wikitable" border = 1
|1||style="background:#FFCC00"|4||style="background:#FFCC00"|5||Прибавим 4 + 1, вычтем 5 - 1.
|-
|1||style="background:#FFCC00"|5||style="background:#FFCC00"|4||Проверяем: 5 > 4, значит прибавим к 5 + 4.
|-
|1||9||style="background:#FFCC00"|4||Удалим последний элемент.
|-
|'''1'''||'''9'''||||Следующее разбиение на слагаемые числа 10.
|}

== Специализация алгоритма для генерации следующего разбиения на подмножества ==

Рассмотрим множество первых n натуральных чисел:<tex>N_n = \{1, 2, ..., n\}</tex>

Упорядочим все разбиения на множества <tex>N_n</tex> лексикографически. Для этого, во-первых, в каждом разбиении упорядочим множества лексикографически. Будем говорить, что подмножество <tex> A \subset N_n </tex> лексикографически меньше подмножества <tex> B \subset N_n </tex> , если верно одно из следующих условий:

*существует <tex>i</tex> такое, что <tex>i \in A</tex> , <tex>i \notin B</tex>, для всех <tex>j < i: j \in A</tex> если и только если <tex>j \in B</tex> , и существует <tex>k > i</tex> такое что <tex>k \in B</tex>;
* <tex> A \subset B </tex> и <tex>i < j</tex> для всех <tex>i \in A</tex> и <tex>j \in B</tex> \ <tex> A </tex>.

Разбиения упорядочены лексикографически следующим образом. Разбиение <tex>N_n = A_1 \cup A_2 \cup . . . \cup A_k</tex> лексикографически меньше разбиения <tex>N_n = B_1 \cup B_2 \cup . . . \cup B_l</tex> если существует такое <tex>i</tex>, что <tex>A_1 = B_1, A_2 = B_2, . . . ,A_{i - 1} = B_{i - 1}, A_i < B_i</tex>.

'''Рассмотрим алгоритм нахождения лексикографически следующего разбиения на подмножества:'''
*Будем хранить подмножества в списке списков, например, разбиение <tex> \{1, 2, 3\} ~ \{4, 5\}</tex> будет выглядеть так:

{| class="wikitable" border = 1
|1||2||3
|-
|4||5||
|}

* Будем поддерживать массив удалённых элементов {{---}} элементы, которые затем нужно будет вернуть в разбиение.

* Двигаясь снизу вверх будем рассматривать подмножества.
** Если мы можем дописать в текущее подмножество минимальный элемент из удалённых, то мы нашли следующее разбиение и нужно завершить цикл.
** Если дописать не можем, значит, либо нужно укоротить и заменить какой-то элемент в текущем подмножестве, либо перейти к следующему подмножеству. Будем идти справа налево и рассматривать элементы:
*** Если мы можем заменить текущий элемент минимальным удалённым {{---}} мы нашли следующее разбиение, завершаем оба цикла и выполняем алгоритм дальше. Стоит отметить, что нельзя перезаписывать последний элемент в подмножестве, иначе мы не сможем дописать минимальный хвост после этого подмножества {{---}} в удалённых будет элемент меньше текущего и мы не сможем выписать удаленные элементы так, чтобы получилось корректное разбиение.
*** Если заменить текущий элемент каким-то из удалённых нельзя, то следует удалить и этот.
* Допишем лексикографически минимальный хвост подмножеств из оставшихся удалённых элементов.

'''list<list<int>>''' nextSetPartition('''list<list<int>>''' a):
used = '''list<int>'''
// a {{---}} список, содержащий подмножества
// used {{---}} список, в котором мы храним удаленные элементы
fl = ''false''
'''for''' i = a.size - 1 '''downto''' 0
'''if''' (used.size != 0) '''and''' (max(used) > a[i][-1]) // в удалённых есть хотя бы один элемент, который мы можем добавить в конец.
m = '''минимум из''' used '''строго больше''' a[i][-1]
a[i].add(m) // добавляем
used.remove(m)
'''break'''
'''for''' j = a[i].size - 1 '''downto''' 0
'''if''' (used.size != 0) '''and''' (j != 0) '''and''' (max(used) > a[i][j]) // если можем заменить элемент, другим элементом из списка used и он не последний
m = '''минимум из''' used '''строго больше''' a[i][j]
old = a[i][j]
a[i][j] = m // заменяем
used.remove(m)
used.add(old)
fl = ''true''
'''break'''
'''else'''
used.add(a[i][-1])
a[i].pop()
'''if''' a[i].size == 0
a.pop()
'''if''' fl
'''break'''
// далее выведем все удалённые, которые не выбрали
sort(used)
'''for''' i = 0 '''to''' used.size - 1
a.add('''list<int>'''(used[i])) // добавляем лексикографически минимальных хвост
'''return''' a

=== Пример работы ===

'''Рассмотрим следующее разбиение:'''

{| class="wikitable" border = 1
|1||2||3
|-
|4||5||
|}

'''1 Шаг:'''

{| class="wikitable" border = 1
|1||2||3||
|-
|4||style="background:#FFCC00"|5||||
|-
| ||^|| ||Удалили элемент 5.
|-
| || || ||Удалённые элементы
|}

'''2 Шаг:'''

{| class="wikitable" border = 1
|1||2||3||
|-
|style="background:#FFCC00"|4|| ||||
|-
|^|| || ||Удалили элемент 4. Так как он является последним в подмножестве, то мы не можем заменить его на другой.
|-
|5|| || ||Удалённые элементы
|}

'''3 Шаг:'''

{| class="wikitable" border = 1
|1||2||3||style="background:#FFCC00"|4||
|-
| || || ||^||Дополнили первое подмножество элементом 4
|-
|5|| || || ||Удалённые элементы
|}

'''4 Шаг:'''

{| class="wikitable" border = 1
|1||2||3||4||
|-
|style="background:#FFCC00"|5|| || || ||Дописали лексикографически минимальный хвост
|-
| || || || ||Удалённые элементы
|}

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

== Источники информации ==

* [http://rain.ifmo.ru/cat/view.php/vis/combinations/permutations-2000 Визуализатор перестановок]
* [http://cppalgo.blogspot.com/2011/02/episode-2.html Пример компактного кода для перестановок (С++)]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

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

2021-12-31T10:33:00Z

Npanuhin: Лишняя переменная P, кол-во перестановок = n!

== Описание алгоритма ==
Номер данного [[Комбинаторные объекты|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <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 // перебираем элементы комбинаторного объекта
'''for''' j = 1 '''to''' a[i] - 1 // перебираем элементы, в лексикографическом порядке меньшие рассматриваемого
'''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 // <tex>n</tex> {{---}} количество элементов в перестановке
'''for''' j = 1 '''to''' a[i] - 1 // перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте
'''if''' was[j] == ''false'' // если элемент <tex>j</tex> ранее не был использован
numOfPermutation += (n - i)! // все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых
меньше нашего в лексикографическом порядке, идут раньше данной перестановки
was[a[i]] = ''true'' // <tex>i</tex>-й элемент использован
'''return''' numOfPermutation

Асимптотика алгоритма {{---}} <tex>O(n ^ 2) </tex> и <tex>O(n) </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>:


<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>


'''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] // прибавляем количество перестановок, которые могли начинаться с <tex>j</tex>
sum += part[i] // увеличиваем уже поставленную сумму
last = part[i] // обновляем последний поставленный элемент 
'''return''' numOfPart // возвращаем ответ

Стоит отметить, что количество итераций вложенного цикла не более, чем <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
*Дискретная математика. Теория и практика решения задач по информатике / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2008.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]