Алгоритмы и структуры данных (ADS-9)

Срок выполнения задания:

по 07.06.2026

Задача

Разработать версию дерева вариантов (возможностей) для генерации всех перестановок заданного набора символов (элементов типа char)

Пояснение

Одной из задач комбинаторики является генерация всех перестановок элементов. Возьмем, к примеру, цифры 1,2,3. Из этих цифр можно образовать следующие последовательности:

123
132
213
231
312
321

В качестве решения задачи генерации всех перестановок можно использовать дерево вариантов.

Рассмотрим пример с генерацией всех перестановок из множества цифр 1,3,5,7 (см. рис.)

На первом уровне используются цифры 1,3,5,7. Количество узлов в дереве на этом уровне соответствует количеству цифр, то есть 4. От каждого узла вниз отходят по три связи к узлам, в которых находятся оставшиеся цифры в множестве (например 3,5,7 для 1). Передвигаясь на уровень ниже мы можем использовать цифры, которые не встречаются на пути от корня. На уровне три мы можем организовать не более двух связей для каждого узла.

Если опуститься еще на один уровень, то связей будет по одной. Так, от цифры 5 мы можем образовать потомка с 7, а от 7 - 5.

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

Если двигаться от корня к листьям, мы будем получать возможные комбинации. Эти комбинации должны приводить к получению упорядоченных по возрастанию "чисел", например:

1357
1375
1537
1573
...

Алгоритм построения дерева

Перед началом необходимо разработать узел дерева, в котором будет находиться вектор из указателей на узлы нижнего уровня.

1. Вызываем первый раз функцию построения дерева с вектором из исходных элементов (например, 1,3,5,7).
2. Для корня дерева образуем потомков по числу цифр в векторе (например, как на рисунке четыре).
3. Вызываем функцию построения дерева рекурсивно и передаем ей вектор из оставшихся цифр. То есть, для узла с 1 массив должен содержать 3,5,7.
4. Образуем потомков и присваиваем им значения из вектора.
5. Рекурсивно для каждого потомка передаем вектор из двух элементов.
6. Рекурсия должна остановится, когда передаваемый вектор будет пустой.

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

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

Задание №1

Построить дерево вариантов для заданного вектора символов PMTree. Конструктор дерева принимает на вход вектор символов.

// определяем входной вектор для дерева
std::vector<char> in = {'1','2','3'};

// создаем дерево
PMTree tree(in);

Задание №2

Реализовать функцию getAllPerms, возвращающий все перестановки в виде вектора векторов символов. Заголовок данной функции включается в файл include/tree.h

Пример:

// определяем входной вектор для дерева
std::vector<char> in = {'1','2','3'};

// создаем дерево
PMTree tree(in);

// получаем все перестановки
std::vector<std::vector<char>> perms = getAllPerms(tree);

Задание №3

Необходимо разработать функцию, которая получает из дерева перестановку с определенным номером. например, для рассмотренного случая с цифрами 1,3,5,7, перестановка №1 должна соответствовать строке "1357", а перестановка №2 - "1375". Реализовать такую функцию можно двумя способами:

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

Данное решение имеет очевидный недостаток: низкая скорость работы, поскольку для каждой N-ой перестановки нужно получить N-1, а потом выдать нужную.

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

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

Необходимо разработать две функции, реализующие эти подходы:

• getPerm1(PMTree& tree, int num)
• getPerm2(PMTree& tree, int num)

Заголовки данных функций включаются в файл include/tree.h

Пример:

// определяем входной вектор для дерева
std::vector<char> in = {'1','2','3'};

// создаем дерево
Tree tree(in);

// запрашиваем первую перестановку
std::vector<char> result1 = getPerm1(tree, 1);  //  123

// запрашиваем вторую перестановку
std::vector<char> result2 = getPerm2(tree, 2);  //  132
...

Задание №4

Провести вычислительный эксперимент, измеряя время работы функций getPermAll(), getPerm1(), getPerm2() в зависимости от размера алфавита символа для перестановок (n). Номера перестановок для получения генерировать случайно.

Построить график зависимостей времени работы функций от n. Использовать логарифмический масштаб вертикальной оси. Сохранить график в файле result/plot.png.

Примечание

Если перестановки с указанным номером не существует, то должен возвращаться пустой вектор.

Состав проекта

В файл include/tree.h необходимо поместить описание дерева Tree с основными функциями. Класс Tree реализуется для элементов типа char.

В файл src/alg.cpp поместить реализацию функций getAllPerms(), getPerm1(), getPerm2(). Заголовки этих функций должны содержаться в include/tree.h

Файл src/main.cpp должен содержать примеры получения перестановок и текст эксперимента с замерами времени.

График по результатам проведения вычислительного эксперимента: result/plot.png.