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

перестановок.

вход вектор и множество
Множество реализуем бинарным вектором
Также будем передавать

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

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;
}
}
}

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;
}