JakimPL

Kombinacje

Apr 20th, 2020
411
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <map>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <random>
  6.  
  7. constexpr int start = 10;
  8. constexpr int fs = 3;
  9. constexpr double p = 2.0f / 9;
  10. constexpr long games = 100000000;
  11.  
  12. template <typename T>
  13. std::string printVector(std::vector<T> v, int offset = 1)
  14. {
  15.     std::string s;
  16.     unsigned int n = v.size();
  17.     for (unsigned int i = 0; i < n; ++i) {
  18.         s += std::to_string(v[i] + offset);
  19.         if (i < n - 1) {
  20.             s += ", ";
  21.         }
  22.     }
  23.  
  24.     return s;
  25. }
  26.  
  27. unsigned long binomialCoefficient(unsigned int n, unsigned int k)
  28. {
  29.     unsigned long result = 1;
  30.  
  31.     // zachodzi tozsamosc (n, k) = (n, n - k)
  32.     if (k > n - k) {
  33.         k = n - k;
  34.     }
  35.  
  36.     for (unsigned int i = 0; i < k; ++i) {
  37.         result *= n - i;
  38.         result /= i + 1;
  39.     }
  40.  
  41.     return result;
  42. }
  43.  
  44. bool isCombinationOk(unsigned int n, std::vector<unsigned long> combination)
  45. {
  46.     unsigned int r = start;
  47.     std::sort(combination.rbegin(), combination.rend());
  48.     for (unsigned int i = 0; i < n; ++i) {
  49.         if (i == combination.back()) {
  50.             combination.pop_back();
  51.             r += fs;
  52.         }
  53.  
  54.         if (i >= r - 1) {
  55.             return false;
  56.         }
  57.     }
  58.  
  59.     return true;
  60. }
  61.  
  62. unsigned long chooseCombinationSimple(unsigned int n, unsigned int k)
  63. {
  64.     // przypadki krancowe mozna rozwiazac od razu
  65.     unsigned long number = 0;
  66.     if (k > 0 && k <= n) {
  67.         // algorytm dla k >= 1
  68.         std::vector<unsigned long> indices;
  69.  
  70.         for (unsigned int index = 0; index < k; ++index) {
  71.             indices.push_back(index);
  72.         }
  73.  
  74.         // przygotowujemy wszystkie mozliwe kombinacje wraz z wagami, by utworzyc CDF (dyskretna dystrybuante)
  75.         bool end = false;
  76.         while (!end) {
  77.  
  78.             if (isCombinationOk(n, indices)) {
  79.                 std::cout << printVector(indices) << "\n";
  80.                 number++;
  81.             }
  82.  
  83.             // algorytm uklada kombinacje wraz z porzadkiem rosnacym
  84.             // polega on na zwiekszaniu ostatniego indeksu do momentu az to mozliwe, w przeciwnym razie zwiekszamy przedostatni, a nastepne ustawiamy bezposrednio za tym i proces kontynuujemy
  85.             unsigned int id = k - 1;
  86.             while (true) {
  87.                 if (id == k - 1) {
  88.                     if (indices[id] < n - 1) {
  89.                         indices[id]++;
  90.                         break;
  91.                     }
  92.                     // dla przypadku count = 1 algorytm konczy sie po przejsciu calej listy jednokrotnie
  93.                     else if (k == 1) {
  94.                         end = true;
  95.                         break;
  96.                     }
  97.                 } else if (id < k - 1 && indices[id] + 1 != indices[id + 1]) {
  98.                     indices[id]++;
  99.                     break;
  100.                 }
  101.  
  102.                 // jezeli nie da sie zwiekszyc indeksu, zwiekszamy indeks poprzedniego i ustawiamy nastepne indeksy bezposrednio za indeksem poprzedniego
  103.                 indices[id - 1] += 1;
  104.                 for (unsigned int idx = id; idx < k; ++idx) {
  105.                     indices[idx] = indices[idx - 1] + 1;
  106.                 }
  107.  
  108.                 // jezeli nie da sie juz zwiekszyc indeksu, przechodzimy na poprzedni
  109.                 if (indices[id - 1] == n - k + id) {
  110.                     id--;
  111.                     if (id == 0) {
  112.                         end = true;
  113.                         break;
  114.                     }
  115.                 } else {
  116.                     break;
  117.                 }
  118.             }
  119.         }
  120.     }
  121.  
  122.     return number;
  123. }
  124.  
  125. int main(int argc, char **argv)
  126. {
  127.     bool run = (argc >= 2);
  128.     if (run) {
  129.         unsigned int k = std::atoi(argv[1]);
  130.         std::cout << chooseCombinationSimple(start + fs * (k - 1), k) << "\n";
  131.     } else {
  132.         unsigned long total = 0;
  133.         std::map<unsigned int, unsigned int> hits;
  134.         std::random_device rd;
  135.         std::mt19937 e2(rd());
  136.         std::uniform_real_distribution<> dist(0, 1);
  137.  
  138.         for (unsigned int game = 0; game < games; ++game) {
  139.             unsigned int i = 0;
  140.             unsigned int r = start;
  141.             while (i < r) {
  142.                 if (dist(e2) < p) {
  143.                     r += fs;
  144.                 }
  145.  
  146.                 i++;
  147.             }
  148.  
  149.             hits[i]++;
  150.             total += i;
  151.         }
  152.  
  153.         for (std::pair<unsigned int, unsigned int> element : hits) {
  154.             std::cout << element.first << ": " << static_cast<double>(element.second) / games << "\n";
  155.         }
  156.         std::cout << "AVERAGE: " << static_cast<double>(total) / games << "\n";
  157.     }
  158.  
  159.     return 0;
  160. }
RAW Paste Data