Kombinacje

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <random>

constexpr int start = 10;
constexpr int fs = 3;
constexpr double p = 2.0f / 9;
constexpr long games = 100000000;

template <typename T>
std::string printVector(std::vector<T> v, int offset = 1)
{
    std::string s;
    unsigned int n = v.size();
    for (unsigned int i = 0; i < n; ++i) {
        s += std::to_string(v[i] + offset);
        if (i < n - 1) {
            s += ", ";
        }
    }

    return s;
}

unsigned long binomialCoefficient(unsigned int n, unsigned int k)
{
    unsigned long result = 1;

    // zachodzi tozsamosc (n, k) = (n, n - k)
    if (k > n - k) {
        k = n - k;
    }

    for (unsigned int i = 0; i < k; ++i) {
        result *= n - i;
        result /= i + 1;
    }

    return result;
}

bool isCombinationOk(unsigned int n, std::vector<unsigned long> combination)
{
    unsigned int r = start;
    std::sort(combination.rbegin(), combination.rend());
    for (unsigned int i = 0; i < n; ++i) {
        if (i == combination.back()) {
            combination.pop_back();
            r += fs;
        }

        if (i >= r - 1) {
            return false;
        }
    }

    return true;
}

unsigned long chooseCombinationSimple(unsigned int n, unsigned int k)
{
    // przypadki krancowe mozna rozwiazac od razu
    unsigned long number = 0;
    if (k > 0 && k <= n) {
        // algorytm dla k >= 1
        std::vector<unsigned long> indices;

        for (unsigned int index = 0; index < k; ++index) {
            indices.push_back(index);
        }

        // przygotowujemy wszystkie mozliwe kombinacje wraz z wagami, by utworzyc CDF (dyskretna dystrybuante)
        bool end = false;
        while (!end) {

            if (isCombinationOk(n, indices)) {
                std::cout << printVector(indices) << "\n";
                number++;
            }

            // algorytm uklada kombinacje wraz z porzadkiem rosnacym
            // 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
            unsigned int id = k - 1;
            while (true) {
                if (id == k - 1) {
                    if (indices[id] < n - 1) {
                        indices[id]++;
                        break;
                    }
                    // dla przypadku count = 1 algorytm konczy sie po przejsciu calej listy jednokrotnie
                    else if (k == 1) {
                        end = true;
                        break;
                    }
                } else if (id < k - 1 && indices[id] + 1 != indices[id + 1]) {
                    indices[id]++;
                    break;
                }

                // jezeli nie da sie zwiekszyc indeksu, zwiekszamy indeks poprzedniego i ustawiamy nastepne indeksy bezposrednio za indeksem poprzedniego
                indices[id - 1] += 1;
                for (unsigned int idx = id; idx < k; ++idx) {
                    indices[idx] = indices[idx - 1] + 1;
                }

                // jezeli nie da sie juz zwiekszyc indeksu, przechodzimy na poprzedni
                if (indices[id - 1] == n - k + id) {
                    id--;
                    if (id == 0) {
                        end = true;
                        break;
                    }
                } else {
                    break;
                }
            }
        }
    }

    return number;
}

int main(int argc, char **argv)
{
    bool run = (argc >= 2);
    if (run) {
        unsigned int k = std::atoi(argv[1]);
        std::cout << chooseCombinationSimple(start + fs * (k - 1), k) << "\n";
    } else {
        unsigned long total = 0;
        std::map<unsigned int, unsigned int> hits;
        std::random_device rd;
        std::mt19937 e2(rd());
        std::uniform_real_distribution<> dist(0, 1);

        for (unsigned int game = 0; game < games; ++game) {
            unsigned int i = 0;
            unsigned int r = start;
            while (i < r) {
                if (dist(e2) < p) {
                    r += fs;
                }

                i++;
            }

            hits[i]++;
            total += i;
        }

        for (std::pair<unsigned int, unsigned int> element : hits) {
            std::cout << element.first << ": " << static_cast<double>(element.second) / games << "\n";
        }
        std::cout << "AVERAGE: " << static_cast<double>(total) / games << "\n";
    }

    return 0;
}