Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cassert>
- #include <queue>
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- const int MAXN = 16; // размерность нашей задачи
- // массив a[] будет содержать в себе текушую рассматриваемую перестановку
- int a[MAXN], n, k;
- int main()
- {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- cin >> n >> k;
- // инициализируем массив a[]
- // он будет заполнен "0" и "1"
- // изачально он будет вида "000000000000011111111"
- // причем первые k нули, последние n - k единицы, всего n элементов
- // ноль означает, что этот элемент с номером i сейчас участвует в перестановке
- // например "01000101" означает перестановку "02346"
- // или же "13457", если нумеровать с единицы (как и нужно в задаче)
- for (int i = 0; i < n - k; i++)
- a[n - i - 1] = 1;
- // за одну итерацию цикла выводим одну перестановку
- // цикл с постусловием, так как одна перестановка точно будет
- do
- {
- // перебираем все элементы массива a
- for (int i = 0; i < n; i++)
- {
- // если на i-ой позиции ноль, то выводим i + 1
- if (a[i] == 0)
- {
- cout << i + 1 << ' ';
- }
- }
- cout << '\n';
- } while (next_permutation(a, a + n));
- // функция next_permutation принимает на вход указатель на начало и конец памяти
- // a - указатель на начало массива, a + n - указатель на конец массива
- // генерирует следующую лексикографическую перестановку в данном массиве, изменяя его
- // возвращает false если перестановка последняя, иначе true
- // то есть после до в массиве a была перестановка "0010101", то после будет "0010110"
- // и функция вернет true, то есть цикл продолжит выполнение
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement