Строки – 3

В этой теме рассмотрим некоторые понятия из комбинаторики, а также алгоритмы генерации перестановок и строк.

Правило произведения

Это основное комбинаторное правило, на котором основан подсчет количества вариантов выбора объектов и их совокупностей.

Если объект \(A\) можно выбрать \(n\) способами, а объект \(B\) можно выбрать m способами, то пары \((A, B)\) можно выбрать \(m \cdot n\) способами. Проиллюстрировать корректность этого правила можно на примере корзин с яблоками: если у вас есть \(n\) корзин и в каждой находится по \(m\) яблок, то всего у вас $n m $ яблок. Так и объектами: для каждого из n объектов \((A_1, A_2, \dots, A_n)\) можно выбрать в пару любой из m объектов \((B_1, B_2, \dots, B_m)\), поэтому для получения количества пар вы умножаем эти величины.

Количество перестановок

Без повторений

Пусть у нас есть набор из \(n\) уникальных объектов: \(A_1, A_2, \dots, A_n\). Если мы расположим эти объекты в определенном порядке, то мы рассмотрим одну из перестановок такого набор. Например, переставим первые \(2\) элемента (также это называется транспозицией): получится \(A_2, A_1, A_3, A_4, \dots, A_n\)

Найдем количество перестановок рассуждением по правилу произведения. У нас есть n объектов и n мест. На первое место можно поставить любой из n объетов. На второе место можно поставить любой объект, кроме расставленного на первое место. На третье – все, кроме использованных на первом и втором местах. И так далее. В итоге получается произведение, которое сворачивается в факториал:

\[ n \cdot (n - 1) \cdot \dots 2 \cdot 1 = n! \]

Говорят, что существует \(n!\) перестановок на \(n\) элеметах.

С повторениями

Рассмотрим следующий набор букв: \(banana\). Рассмотренная выше формула для количества перестановок требует уникальности элементов, что неверно для слова \(banana\). Пронумеруем повторяющиеся буквы: \(ba_1n_1a_2n_2a_3\). Очевидно, что \(ba_2n_1a_1n_2a_3\) ровно то же самое слово, что и исходное \(banana\), так как мы переставили \(2\) одинаковые буквы \(a\).

Для каждого расположения букв \(b, a, n\) можно переставить буквы \(a\) \(3!\) способами, затем буквы \(n\) \(2!\) способами. Значит, итоговое количество перестановок при повторяющихся буквах – это \(\frac{6!}{3! 2!} = 60\)

Итоговая формула количества перестановок с повторениями:

\[ \frac{n!}{k_1! k_2! \dots k_t!} \]

, где \(n\) — длина строки. \(k_1, k_2, \dots, k_t\) — количества вхождений \(t\) уникальных символов строки.

Генерация перестановок

Рассмотрим генерацию перестановок с помощью рекурсивного алгоритма. Идея рекурсивной функции заключается в следующем:

1. Получаем строку с зафиксированным префиксом

2. Меняем первый незафиксированный элемент последовательно со всеми незафиксированными.

3. Для каждой из таких замен запускаем эту же функцию с зафиксированным префиксом на 1 большей длины

4. Если все позиции строки зафиксированы, то одна из перестановок сгенерирована, ее можно выводить (или сохранять, детали уже зависят от перестановки задачи)

#include <iostream>
#include <string>
#include <algorithm>

void generate(int last_idx, int length, std::string& s) {
    if (last_idx == length - 1) { // Вывод очередной перестановки
        // Вывод очередной перестановки
        return;
    }
    for (int j = last_idx; j < length; ++j) {  // Запускаем процесс обмена
        std::swap(s[last_idx], s[j]);          // a[t] со всеми последующими
        generate(last_idx + 1, length, s);     // Рекурсивный вызов
        std::swap(s[last_idx], s[j]);
    }
}

Код выше рассчитан на работу со строкой. Аналогично можно генерировать перестановки в любом контейнеере, который поддерживает сохранение порядка и доступ по индексу (random access), например, std::vector. Во всех случаях контейнер крайне рекомендуется передавать по ссылке, чтобы избежать лишнего копирования.

Сложность такого алгоритма: \({\cal{O}}(n!)\)

Генерация следующей перестановки

Часто возникает неоходимость обработки каждой из сгенерированной перестановок и рассматривать их в лексикографическом порядке. В этом случае нам бы хотелось получать следующую переставновку лексикографически. С помощью алгоритма Нарайаны это можно делать за линейную сложность: \({\cal{O}}(n)\). Конечно, такая функция будет нерекурсивной.

Чтобы получить следующую перестановку из существующей, нужно сделать следующие шаги:

1. Выбрать самый правый элемент, который меньше своего соседа справа. То есть найти \(\max i: a_i < a_{i + 1}\)

2. Выбрать самый правый элемент, который больше выбранного на первом шаге: \(\max_{l > i} l: a_i < a_l\). Заметим, что такой индекс всегда есть, например. \(l = i + 1\)

3. Поменять местами \(a_i\) и \(a_l\)

4. Записать в обратном порядке элементы: \(a_{i + 1}, a_{i + 2}, \dots, a_n\)

Заметим, что каждый пункт выполняется последовательно и обладает асимптотической сложностью не больше \({\cal{O}}(n)\), что и дает линейную сложность всего алгоритма Нарайаны для генерации следующей перестановки в лексикографическом порядке

Если первый пункт удалось выполнить, то следующая перестановка существует и после ее генерации функция вернет true. Если же элемент в первом пункте найден не был, то следующая перестановка не существует и фукнция должна вернуть false. Действительно, если первый пункт выполнить не удалось, то не существует элемента с большим соседом справа: \(\nexists i: a_i < a_{i + 1} \Rightarrow a_1 > a_2 > \dots > a_n\), то есть все элементы расположены по убыванию, а это последнее расположения при лексикографическом порядке.

Такая работа с булевыми возвращаемыми значениями позволяет использовать следующий синтаксис при работе с перестановками:

data = ...
while (nextPermutation(data)) { // создание новой перестановки, true и обработка перестановки. Или false и выход из цикла
    // обработки очередной перестановки, сохраненной в data
}

Также важно сказать, что в STL есть встроенные фукнции, которые принимают итераторы на диапазон/диапазоны для генерации следующей или предыдущей перестановки, а также для определения, является ли одна последовательность перестановокй другой.

namespace std {
    bool next_permutation(it_1, it_2);
    bool prev_permutation(it_1, it_2);

    bool is_permutation(it_11, it_12,
                        it_21, it_22);
};

Правильные скобочные последовательности

Будем рассмаривать только 1 тип скобок.

Скобочная последовательность – любой набор открывающих и закрывающих скобок допустимых типов (мы будем рассматривать задачу в более простой постановке: только один тип скобок – круглые).

Формаль правильная последовательность скобочная последотельность задается рекуррентно:

• пустая последовательность – правильная

• \((A)\) – правильная, если \(A\) – правильная

• \(AB\) – правильная, если \(A\) и \(B\) – правильные

Как провереть скобочные последовательности на правильность? По определению и логике во всей строке открывающих скобок должно быть столько же, сколько закрывающих. Также любой префикс должен содержать закрывающих скобок не больше, чем открывающих. Введем понятие баланса скобок для \(i\)-того префикса: \(\text{balance}_i := \text{open}_i - \text{close}_i\), то есть разница между количествами открытых и закрытых. Тогда \(\forall i: \text{balance}_i \ge 0\) и \(\text{balance}_n = 0\).

Проверить это легко.

для каждого символа:
    если скобка открывающая, то увеличиваем баланс на 1
    если скобка закрывающая, то уменьшаем баланс на 1

    если баланс отрицательный, то последовательность неправильная, выходим

если баланс по итогу равен 0 и всегда был неотрицательным, то последовательность правильная

Теперь разберем, как сгенерировать все правильные скобочные последовательности определенной длины. Длина скобочной последовательности всегда четная: ровно половина открывающих скобок, остальные – закрывающие.

Рассмотрим рекурсивную функцию, которая позволит построить дерево перебора (как в задаче “Монетки”). Пусть у нас есть префикс сгенерированной последовательности, который точно не нарушает правил построение правильных последовательностей.

• если открывающих скобок открывающих не больше половины требуемой длины, то можем добавить открывающую скобку

• если открывающих больше, чем закрывающих, то можем добавить закрывающую скобку

// half_length -- требуемое количество открывающих скобок, оно равно половине от требуемой длины
generate(int half_length, int open, int close, string current):
   if counter_open + counter_close == 2 * half_length:
       // вывод последовательности
       return
   if counter_open < half_length:
       // рекурсивный запуск, добавляя открывающую скобку
       // важно не забыть изменить счетчик открывающих скобок, который передается как аргумент
   if counter_open > counter_close:
       // рекурсивный запуск, добавляя закрывающую скобку
       // важно не забыть изменить счетчик закрывающих скобок, который передается как аргумент