Step by Step solution about How to resolve the algorithm Permutation test step by step in the C++ programming language

This C++ program calculates the number of possible combinations of selecting a subset of elements from a given set, where the sum of the selected elements is less than or greater than a specified threshold. It uses mathematical formulas and dynamic programming techniques to efficiently determine these combinations.

Here's a detailed breakdown of the code:

1. Class combinations:

   • Defines a class with a single public member function operator().
   • This function takes two integer arguments, n (the total number of elements) and k (the number of elements to select), and calculates the number of combinations of selecting k elements from n elements.
   • It internally uses two private member functions:
     • partial_factorial(from, to): Calculates the partial factorial of from elements from to elements inclusive.
     • factorial(n): Calculates the factorial of n.

2. main() Function:

   • Defines a constant treatment with a value of 9.
   • Initializes a vector data containing 20 integer values representing the elements of the set.
   • Calculates the sum of the first treatment elements in data.

3. Function pick:

   • A lambda function that takes three integer arguments: n (the number of elements to select), from (the starting index in the data vector), and accumulated (the current sum of selected elements).
   • It recursively iterates through the elements of the data vector starting from index from to calculate the number of ways to select n elements such that the sum of selected elements is greater than or equal to treated.

4. Calculating Combinations and Probabilities:

   • Calculates the total number of possible combinations using the combinations class: total = combinations(data.size(), treatment). -Calculates the number of combinations where the sum of selected elements is greater than treated: greater = pick(treatment, data.size(), 0). -Subtracts greater from total to get the number of combinations where the sum is less than or equal to treated: lesser = total - greater.
   • Prints the percentage and count of combinations where the sum is less than or equal to and greater than treated.

The output of the program shows that 87.197168% (80551) of the combinations have a sum less than or equal to the treated value, while 12.802832% (11827) have a sum greater than the treated value.

#include<iostream>
#include<vector>
#include<numeric>
#include<functional>

class
{
public:
    int64_t operator()(int n, int k){ return partial_factorial(n, k) / factorial(n - k);}
private:
    int64_t partial_factorial(int from, int to) { return from == to ? 1 : from * partial_factorial(from - 1, to); }
    int64_t factorial(int n) { return n == 0 ? 1 : n * factorial(n - 1);}
}combinations;

int main()
{
    static constexpr int treatment = 9;
    const std::vector<int> data{ 85, 88, 75, 66, 25, 29, 83, 39, 97,
                                 68, 41, 10, 49, 16, 65, 32, 92, 28, 98 };

    int treated = std::accumulate(data.begin(), data.begin() + treatment, 0);

    std::function<int (int, int, int)> pick;
    pick = [&](int n, int from, int accumulated)
            {
                if(n == 0)
                    return accumulated > treated ? 1 : 0;
                else
                    return pick(n - 1, from - 1, accumulated + data[from - 1]) +
                            (from > n ? pick(n, from - 1, accumulated) : 0);
            };

    int total   = combinations(data.size(), treatment);
    int greater = pick(treatment, data.size(), 0);
    int lesser  = total - greater;

    std::cout << "<= : " << 100.0 * lesser  / total << "%  " << lesser  << std::endl
              << " > : " << 100.0 * greater / total << "%  " << greater << std::endl;
}


<= : 87.197168%  80551
 > : 12.802832%  11827