Advertisement
Guest User

Untitled

a guest
Jun 26th, 2019
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.56 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cassert>
  3. #include <queue>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cstring>
  7. using namespace std;
  8.  
  9. const int MAXN = 16; // размерность нашей задачи
  10.  
  11. // массив a[] будет содержать в себе текушую рассматриваемую перестановку
  12. int a[MAXN], n, k;
  13.  
  14. int main()
  15. {
  16.     freopen("input.txt", "r", stdin);
  17.     freopen("output.txt", "w", stdout);
  18.  
  19.     cin >> n >> k;
  20.  
  21.     // инициализируем массив a[]
  22.     // он будет заполнен "0" и "1"
  23.     // изачально он будет вида "000000000000011111111"
  24.     // причем первые k нули, последние n - k единицы, всего n элементов
  25.     // ноль означает, что этот элемент с номером i сейчас участвует в перестановке
  26.     // например "01000101" означает перестановку "02346"
  27.     // или же "13457", если нумеровать с единицы (как и нужно в задаче)
  28.     for (int i = 0; i < n - k; i++)
  29.         a[n - i - 1] = 1;
  30.  
  31.  
  32.     // за одну итерацию цикла выводим одну перестановку
  33.     // цикл с постусловием, так как одна перестановка точно будет
  34.     do
  35.     {
  36.         // перебираем все элементы массива a
  37.         for (int i = 0; i < n; i++)
  38.         {
  39.             // если на i-ой позиции ноль, то выводим i + 1
  40.             if (a[i] == 0)
  41.             {
  42.                 cout << i + 1 << ' ';
  43.             }
  44.         }
  45.         cout << '\n';
  46.     } while (next_permutation(a, a + n));
  47.  
  48.     // функция next_permutation принимает на вход указатель на начало и конец памяти
  49.     // a - указатель на начало массива, a + n - указатель на конец массива
  50.     // генерирует следующую лексикографическую перестановку в данном массиве, изменяя его
  51.     // возвращает false если перестановка последняя, иначе true
  52.  
  53.     // то есть после до в массиве a была перестановка "0010101", то после будет "0010110"
  54.     // и функция вернет true, то есть цикл продолжит выполнение
  55.  
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement