🗊Презентация Простейшие переборные задачи. Генерация подмножеств и перестановок

Простейшие переборные задачи: генерация подмножеств и перестановок Лабораторная работа №1 Раздел: комбинаторика

Цель занятия: Изучение простейших переборных задач: генерация подмножеств и перестановок.

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

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

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

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

Генерация множества перестановок Реализуем этот способ Необходима функция, принимающая на вход вектор и множество Множество реализуем бинарным вектором Также будем передавать число элементов, которые еще необходимо добавить к вектору: если оно равно нулю, значит, перестановка построена

Генерация множества перестановок void GenPermut(size_t elems, vector<size_t>& cur, vector<bool>& used) { if (elems == cur.size()) { for (size_t i = 0; i < cur.size() - 1; ++i) { cout << cur[i] + 1 << " "; } cout << cur[cur.size() - 1] + 1 << "\n"; } for (size_t next = 0; next < elems; ++next) { if (!used[next]) { cur.push_back(next); used[next] = true; GenPermut(elems, cur, used); cur.pop_back(); used[next] = false; } } }

Построение перестановки по ее номеру

Построение перестановки по ее номеру

Построение перестановки по ее номеру

Построение перестановки по ее номеру

Построение перестановки по ее номеру vector<size_t> Permutation(size_t elemCount, size_t permNumber) { vector<size_t> numbers; for (size_t i = 0; i < elemCount; ++i) { numbers.push_back(i); } int64 currentElementsCount = elemCount; vector<size_t> ans; while (currentElementsCount > 0) { int64 k = 0; int64 L = fact(currentElementsCount - 1); while ((k + 1) * L < permNumber) { ++k; } size_t curNumber = -1; for (size_t j = 0; j < elemCount; ++j) { if (numbers[j] != -1) { ++curNumber; } if (curNumber == k) { ans.push_back(numbers[j] + 1); numbers[j] = -1; break; } } permNumber -= L*k; --currentElementsCount; } return ans; }

Задания

Задания