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

Сентябрь 14, 2022

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

Содержание

2. Цель занятия: Изучение простейших переборных задач: генерация подмножеств и перестановок.
3. Генерация множества перестановок
4. Генерация множества перестановок
5. Генерация множества перестановок
6. Генерация множества перестановок
7. Генерация множества перестановок Реализуем этот способ Необходима функция, принимающая на вход вектор и множество Множество реализуем
8. Генерация множества перестановок void GenPermut(size_t elems, vector & cur, vector & used) { if (elems ==
9. Построение перестановки по ее номеру
10. Построение перестановки по ее номеру
11. Построение перестановки по ее номеру
12. Построение перестановки по ее номеру
13. Построение перестановки по ее номеру vector Permutation(size_t elemCount, size_t permNumber) { vector numbers; for (size_t i
14. Задания
16. Скачать презентацию

Слайд 2

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

Слайд 3

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

Слайд 4

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

Слайд 5

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

Слайд 6

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

Слайд 7

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

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

Слайд 8

Генерация множества перестановок
void GenPermut(size_t elems, vector& cur, vector& 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;
}
}
}

Слайд 9

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

Слайд 10

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

Слайд 11

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

Слайд 12

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

Слайд 13

$Построение перестановки по ее номеру vector Permutation(size_t elemCount, size_t permNumber) {$

Построение перестановки по ее номеру
vector Permutation(size_t elemCount, size_t permNumber) {

vector numbers;
for (size_t i = 0; i < elemCount; ++i) {
numbers.push_back(i);
}
int64 currentElementsCount = elemCount;
vector 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;
}

Слайд 14