fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <set>
  5. #include <random>
  6. #include <ctime>
  7.  
  8. long GetCombinations(std::vector<double> nums) {
  9.     long combinations = 0;
  10.     std::sort(nums.begin(), nums.end());
  11.     std::set<std::multiset<double>> super_set;
  12.  
  13.     do {
  14.         std::multiset<double> multi_set;
  15.  
  16.         for (unsigned int i = 0; i < nums.size() / 2; ++i)
  17.             multi_set.insert(nums[i]);
  18.  
  19.         auto el = (super_set.insert(multi_set));
  20.  
  21.         if (el.second)
  22.             ++combinations;
  23.  
  24.     } while (std::next_permutation(nums.begin(), nums.end()));
  25.  
  26.     return combinations;
  27. }
  28.  
  29. unsigned long int getCombinationCount(std::vector<double> nums) {
  30.  
  31.     unsigned long int n = nums.size();
  32.     unsigned long int n2 = n / 2;
  33.     unsigned long int numUnique = 1;
  34.     unsigned long int numCombinations;
  35.  
  36.     std::sort(nums.begin(), nums.end());
  37.     std::vector<int> numReps;
  38.  
  39.     double testVal = nums[0];
  40.     numReps.push_back(1);
  41.  
  42.     for (std::size_t i = 1; i < n; ++i) {
  43.         if (nums[i] != testVal) {
  44.             numReps.push_back(1);
  45.             testVal = nums[i];
  46.             ++numUnique;
  47.         } else {
  48.             ++numReps[numUnique - 1];
  49.         }
  50.     }
  51.  
  52.     int myMax, r = n2 + 1;
  53.     std::vector<double> triangleVec(r);
  54.     std::vector<double> temp(r);
  55.     double tempSum;
  56.  
  57.     myMax = r;
  58.     if (myMax > numReps[0] + 1)
  59.         myMax = numReps[0] + 1;
  60.  
  61.     for (int i = 0; i < myMax; ++i)
  62.         triangleVec[i] = 1;
  63.  
  64.     temp = triangleVec;
  65.  
  66.     for (std::size_t k = 1; k < numUnique; ++k) {
  67.         for (int i = n2; i > 0; --i) {
  68.             myMax = i - numReps[k];
  69.             if (myMax < 0)
  70.                 myMax = 0;
  71.  
  72.             tempSum = 0;
  73.             for (int j = myMax; j <= i; ++j)
  74.                 tempSum += triangleVec[j];
  75.  
  76.             temp[i] = tempSum;
  77.         }
  78.         triangleVec = temp;
  79.     }
  80.  
  81.     numCombinations = (unsigned long int) triangleVec[n2];
  82.  
  83.     return numCombinations;
  84. }
  85.  
  86. int main() {
  87.     unsigned long int countOP, countChallenge;
  88.  
  89.     std::random_device rd;
  90.     std::mt19937 gen(rd());
  91.     std::uniform_int_distribution<int> distribution(1, 10);
  92.  
  93.     std::cout << "randVec is : "; 
  94.  
  95.     std::vector<double> randVec(12);
  96.     for (std::size_t i = 0; i < 12; ++i) {
  97.         randVec[i] = (double) distribution(gen);
  98.         std::cout << randVec[i] << ' ';
  99.     }
  100.  
  101.     std::cout << std::endl;
  102.  
  103.     std::clock_t start_time, end_time;
  104.  
  105.     start_time = clock();
  106.     countChallenge = getCombinationCount(randVec);
  107.     end_time = clock();
  108.  
  109.     std::cout << "time taken with challenge algorithm : " <<
  110.         end_time - start_time << std::endl;
  111.  
  112.     start_time = clock();
  113.     countOP = GetCombinations(randVec);
  114.     end_time = clock();
  115.  
  116.     std::cout << "time taken with original : " <<
  117.         end_time - start_time << std::endl;
  118.  
  119.     std::cout << "The challenge algorithm returns : " << countChallenge << std::endl;
  120.     std::cout << "The original algorithm returns : " << countOP << std::endl;
  121.     return 0;
  122. }
Success #stdin #stdout 2.29s 4320KB
comments (?)
stdin 
Standard input is empty
stdout 
randVec is : 4 2 6 4 9 8 2 4 1 1 6 9 
time taken with challenge algorithm : 8
time taken with original : 2285718
The challenge algorithm returns : 122
The original algorithm returns : 122
https://ideone.com/F8OQXb
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!