Nik_Perepelov

Комбинаторика

Dec 8th, 2021
681
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //1
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. int factorial[13] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600};
  8.  
  9. vector<int> getPermutation(int n, long long k) {
  10.     vector<int> permutation(n);
  11.     vector<bool> used(n + 1);
  12.  
  13.     for (int i = 0; i < n; i++) {
  14.         int usedPermutations = (k - 1) / factorial[n - i - 1] + 1;
  15.         int j = 1, position = 0;
  16.  
  17.         for (; j < n + 1; j++) {
  18.             if (!used[j])
  19.                 position++;
  20.             if (usedPermutations == position)
  21.                 break;
  22.         }
  23.         permutation[i] = j;
  24.         used[j] = true;
  25.         k = (k - 1) % factorial[n - 1 - i] + 1;
  26.     }
  27.     return permutation;
  28. }
  29.  
  30. int main() {
  31.     int n, k;
  32.     cin >> n >> k;
  33.     auto answer = getPermutation(n, k);
  34.     for (auto &i : answer)
  35.         cout << i << ' ';
  36.     return 0;
  37. }
  38.  
  39. // 2
  40. #include <iostream>
  41. #include <vector>
  42.  
  43. using namespace std;
  44.  
  45.  
  46. vector<int> combination;
  47.  
  48. void printCombination() {
  49.     for (int i: combination)
  50.         cout << i << ' ';
  51.     cout << '\n';
  52. }
  53.  
  54. void nextCombination(int i, int n, int k) {
  55.     if (k == 0) {
  56.         printCombination();
  57.         return;
  58.     }
  59.     for (; i <= n - k; i++) {
  60.         combination.push_back(i + 1);
  61.         nextCombination(i + 1, n, k - 1);
  62.         combination.pop_back();
  63.     }
  64. }
  65.  
  66. int main() {
  67.     int n, k;
  68.     cin >> n >> k;
  69.  
  70.     nextCombination(0, n,  k);
  71.  
  72.     return 0;
  73. }
  74.  
  75. //3
  76. #include <iostream>
  77. #include <vector>
  78. using namespace std;
  79.  
  80. int placement_amount(int n, int m) {
  81.     int res = 1;
  82.     for (int i = n; i >= n - m + 1; i--)
  83.         res *= i;
  84.     return res;
  85. }
  86.  
  87. void genPlacementByNum(int m, int n, int k, vector<int> &placement) {
  88.     vector<bool> used(n);
  89.     int _n = n - 1, _k = k - 1;
  90.     for (int i = 0; i < k; i++) {
  91.         int block_cnt = m / placement_amount(_n, _k);
  92.         m -= block_cnt * placement_amount(_n, _k);
  93.         int position = 0;
  94.         block_cnt++;
  95.         while (block_cnt) {
  96.             if (!used[position])
  97.                 --block_cnt;
  98.             position++;
  99.         }
  100.         used[position - 1] = true;
  101.         placement[i] = position;
  102.         _n--; _k--;
  103.     }
  104. }
  105.  
  106.  
  107.     int main() {
  108.         int n, k, m;
  109.         cin >> n;
  110.         cin >> k;
  111.         cin >> m;
  112.         vector<int> ans(k);
  113.         genPlacementByNum(m - 1, n, k, ans);
  114.  
  115.         for (auto &i : ans)
  116.             cout << i << ' ';
  117.         return 0;
  118.     }
RAW Paste Data