Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Разбиение последовательности - это упорядоченное разделение элементов в последовательности на непересекающиеся подмножества, называемые блоками или группами, таким образом, что каждый элемент входит ровно в одну из этих групп. Важно отметить, что порядок элементов в каждой группе сохраняется.

---

Формула

$\Huge P(n, k) = \sum_{i=1}^{k} S(n, i)$ Где:

• $P(n,k)$ - количество разбиений последовательности длиной $n$ на $k$ подпоследовательностей.

• $S(n,i)$ - количество Стирлинговых чисел второго рода, которые представляют собой количество способов разбить последовательность длиной $n$ на $i$ непустых подпоследовательностей, учитывая, что порядок элементов внутри каждой подпоследовательности важен, но порядок самих подпоследовательностей не важен.

Принцип работы

Эта формула даёт общее количество способов разбить последовательность из $n$ элементов на не более чем $k$ подпоследовательностей. Она опирается на сумму всех возможных разбиений от $1$ до $k$ подпоследовательностей с учётом порядка. Распишем каждый шаг:

• Использование Стирлинговых чисел второго рода: Стирлингово число второго рода $S(n,i)$ показывает количество способов разбить $n$ элементов на $i$ непустых подпоследовательностей. Например, $S(5,2)$ — это количество способов разбить 5 элементов на 2 подпоследовательности.

• Суммирование разбиений: В данной формуле мы суммируем все значения $S(n,i)$ для $i$ от 1 до $k$. Это означает, что мы учитываем разбиения, где количество подпоследовательностей может быть любым от $1$ до $k$. Каждое $S(n,i)$ добавляет к общему числу разбиений способы создать $i$ подпоследовательностей из $n$ элементов.

• Подсчёт всех разбиений: Итоговое значение $P(n,k)$ — это общее количество способов разбить последовательность длиной $n$ на $k$ или менее подпоследовательностей, где порядок элементов внутри каждой подпоследовательности важен, а порядок самих подпоследовательностей не важен.

Посчитаем $P(4,2)$, т.е. количество способов разбить последовательность из четырёx элементов на не более чем две подпоследовательности.

Используем формулу $P(4,2)=S(4,1)+S(4,2)$: - $S(4,1)=1$, так как есть только один способ разбить четыре элемента на одну подпоследовательность (все элементы остаются в одном подмножестве). - $S(4,2)=7$, что означает, что существует семь способов разбить четыре элемента на две подпоследовательности.

Теперь подставим значения: $P(4,2)=1+7=8$, $P(4,2)=1+7=8$

Таким образом, существует восемь способов разбить последовательность из четырёx элементов на не более чем две подпоследовательности.

Вычислительная сложность

Для каждой подпоследовательности требуется пройтись по исходной последовательности и проверить включение каждого элемента, что в среднем составляет $O(n)$ операций. Таким образом, общая вычислительная сложность разбиения на все подпоследовательности равна $O(2n⋅n)$, что отражает как экспоненциальный рост количества подпоследовательностей, так и линейные затраты на создание каждой подпоследовательности.

Пространственная сложность

Для хранения всех подпоследовательностей понадобится $O(2n⋅n)$ памяти, так как нужно сохранять каждую подпоследовательность независимо. количество подпоследовательностей растёт как $2n$ при увеличении длины последовательности $n$, и каждая из них требует в среднем $O(n)$ для обработки и хранения.

---

Применение

1. Комбинаторика. Главное применение разбиений подпоследовательностей находится в области комбинаторики. Они используются для решения различных задач, связанных с подсчетом комбинаторных объектов, таких как перестановки, сочетания и размещения.

2. Криптография. В криптографии разбиения могут использоваться для создания или анализа различных методов шифрования и дешифрования.

---

Готовые функции в Python

В Python библиотека itertools предоставляет функции для работы с различными комбинаторными задачами, включая разбиения подпоследовательностей. Некоторые из этих функций включают в себя:

• combinations(iterable, r) - функция генерирует все возможные комбинации длины r из итерируемого объекта. Она может быть адаптирована для создания разбиений путем выбора подходящей длины r.
• groupby(iterable, key=None) - функция используется для группировки элементов в итерируемом объекте на основе заданного ключа. Это можно использовать для создания разбиений с определенным правилом.

---

Готовые функции в C++

В C++ библиотека <algorithm> предоставляет ряд функций, которые могут быть использованы для работы с разбиениями подпоследовательностей, хотя они не являются непосредственно функциями для разбиений.

Эти функции включают в себя std::partition, std::partition_copy, std::stable_partition, которые позволяют перераспределить элементы в последовательности в соответствии с заданным условием.

---

Псевдокод

Функция ВычислитьРазбиенияПодпоследовательности(n):
    Создать двумерный массив РазбиенияПодпоследовательности[n+1][n+1]

    Для i от 0 до n:
        РазбиенияПодпоследовательности[i][0] = 1

    Для i от 1 до n:
        Для j от 1 до n:
            Если j >= i:
                РазбиенияПодпоследовательности[i][j] = РазбиенияПодпоследовательности[i-1][j] + РазбиенияПодпоследовательности[i-1][j-i]
            Иначе:
                РазбиенияПодпоследовательности[i][j] = РазбиенияПодпоследовательности[i-1][j]

    Вернуть РазбиенияПодпоследовательности[n][n]

---

Реализация на Python

Аннотация:
count_partition_subsequences - функция для вычисления количества разбиений числа n на подпоследовательности
n - число, для которого вычисляется количество разбиений на подпоследовательности
dp - двумерный список для хранения результатов подзадач
n - число, для которого вычисляется количество разбиений на подпоследовательности
dp - таблица для хранения промежуточных результатов при вычислении количества разбиений
result - результат вычисления количества разбиений на подпоследовательности для числа n

def count_partition_subsequences(n):
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = 1

    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if j >= i:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - i]
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[n][n]

---

Олимпиадная реализация на С++

Аннотация:
count_par_subseq - функция для вычисления количества разбиений числа n на подпоследовательности
n - число, для которого вычисляется количество разбиений на подпоследовательности
SubseqPar - двумерный вектор для хранения количества разбиений подпоследовательностей

#include <iostream>
#include <vector>
using namespace std;

int count_par_subseq(int n) {
    vector<vector<int>> SubseqPar(n + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= n; ++i) {
        par_count[i][0] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (j >= i) {
                par_count[i][j] = par_count[i - 1][j] + par_count[i - 1][j - i];
            } else {
                partition_count[i][j] = par_count[i - 1][j];
            }
        }
    }
    return SubseqPar[n][n];
}

---

Продуктовая реализация на С++

Аннотация:
count_partition_subsequences - функция для вычисления количества разбиений числа n на подпоследовательности
n - число, для которого вычисляется количество разбиений на подпоследовательности.
SubsequencePartitions - двумерный вектор для хранения количества разбиений подпоследовательностей

#include <iostream>
#include <vector>
using namespace std;

int count_partition_subsequences(int n) {
    vector<vector<int>> SubsequencePartitions(n + 1, vector<int>(n + 1, 0));

    for (int i = 0; i <= n; ++i) {
        SubsequencePartitions[i][0] = 1;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (j >= i) {
                SubsequencePartitions[i][j] = SubsequencePartitions[i - 1][j] + SubsequencePartitions[i - 1][j - i];
            } else {
                SubsequencePartitions[i][j] = SubsequencePartitions[i - 1][j];
            }
        }
    }
    return SubsequencePartitions[n][n];
}