#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <random>
#include <ctime>

long GetCombinations(std::vector<double> nums) {
    long combinations = 0;
    std::sort(nums.begin(), nums.end());
    std::set<std::multiset<double>> super_set;

    do {
        std::multiset<double> multi_set;

        for (unsigned int i = 0; i < nums.size() / 2; ++i)
            multi_set.insert(nums[i]);

        auto el = (super_set.insert(multi_set));

        if (el.second)
            ++combinations;

    } while (std::next_permutation(nums.begin(), nums.end()));

    return combinations;
}

unsigned long int getCombinationCount(std::vector<double> nums) {

    unsigned long int n = nums.size();
    unsigned long int n2 = n / 2;
    unsigned long int numUnique = 1;
    unsigned long int numCombinations;

    std::sort(nums.begin(), nums.end());
    std::vector<int> numReps;

    double testVal = nums[0];
    numReps.push_back(1);

    for (std::size_t i = 1; i < n; ++i) {
        if (nums[i] != testVal) {
            numReps.push_back(1);
            testVal = nums[i];
            ++numUnique;
        } else {
            ++numReps[numUnique - 1];
        }
    }

    int myMax, r = n2 + 1;
    std::vector<double> triangleVec(r);
    std::vector<double> temp(r);
    double tempSum;

    myMax = r;
    if (myMax > numReps[0] + 1)
        myMax = numReps[0] + 1;

    for (int i = 0; i < myMax; ++i)
        triangleVec[i] = 1;

    temp = triangleVec;

    for (std::size_t k = 1; k < numUnique; ++k) {
        for (int i = n2; i > 0; --i) {
            myMax = i - numReps[k];
            if (myMax < 0)
                myMax = 0;

            tempSum = 0;
            for (int j = myMax; j <= i; ++j)
                tempSum += triangleVec[j];

            temp[i] = tempSum;
        }
        triangleVec = temp;
    }

    numCombinations = (unsigned long int) triangleVec[n2];

    return numCombinations;
}

int main() {
    unsigned long int countOP, countChallenge;
    
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> distribution(1, 10);
	
    std::cout << "randVec is : "; 
    
    std::vector<double> randVec(12);
    for (std::size_t i = 0; i < 12; ++i) {
        randVec[i] = (double) distribution(gen);
        std::cout << randVec[i] << ' ';
    }
    
    std::cout << std::endl;
    
    std::clock_t start_time, end_time;
    
    start_time = clock();
    countChallenge = getCombinationCount(randVec);
    end_time = clock();

    std::cout << "time taken with challenge algorithm : " <<
        end_time - start_time << std::endl;
    
    start_time = clock();
    countOP = GetCombinations(randVec);
    end_time = clock();

    std::cout << "time taken with original : " <<
        end_time - start_time << std::endl;
    
    std::cout << "The challenge algorithm returns : " << countChallenge << std::endl;
    std::cout << "The original algorithm returns : " << countOP << std::endl;
    return 0;
}