HellFinger

Untitled

Nov 26th, 2021
1,079
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <unordered_set>
  3. #include <iterator>
  4. #include <math.h>
  5. #include <vector>
  6. #include <algorithm>
  7. using namespace std;
  8.  
  9. void coefficient_gen(int res[], int a_m){
  10.   //res[0] = a_m + 1
  11.   //res[1]  = c
  12.   //res[2] = m
  13.  
  14.   res[0] = a_m + 1;
  15.   if (a_m % 2 == 1){
  16.     res[2] = a_m * a_m;
  17.     res[1] = a_m - 1;
  18.   }
  19.   else if (a_m % 2 == 0 && a_m % 4 == 0){
  20.     res[2] = a_m * a_m;
  21.     res[1] = a_m - 1;
  22.   }
  23.   else{
  24.     res[2] = (a_m * a_m)/2;
  25.     res[1] = a_m - 1;
  26.   }
  27. }
  28.  
  29.  
  30. void lcg(vector<int>& r, int seed, int size, int a, int c, int m){
  31.  
  32.   if (size == 1){
  33.     r.push_back((a*seed+c)%m);
  34.     return;
  35.   }
  36.   for(int i = 0; i < size; ++i){
  37.     r.push_back(0);
  38.   }
  39.   r[0] = seed;
  40.   for(int i = 1; i < size; ++i){
  41.     r[i] = (a*r[i-1]+c)%m;
  42.   }
  43.   r.erase(r.begin());
  44. }
  45.  
  46.  
  47.  
  48. //b = a-1 is sqrt of period or halfed one
  49. //x = |A|+|B|
  50. //y = |A|/|B|
  51. //i2u is intersection volume to union volume
  52.  
  53.  
  54. void generate(vector<int>& set1, vector<int>& set2, int seed, int b, double i2u, double y){
  55.   int acm[3];
  56.   coefficient_gen(acm, b);
  57.   int i = int(round(i2u*acm[2]));
  58.   double proportion = (acm[2]*y-i)/(acm[2]-i*y);
  59.   vector<int> uniSet;
  60.   lcg(uniSet, seed, acm[2] + i, acm[0], acm[1], acm[2]);
  61.   vector<int>::iterator setWalker1 = uniSet.begin();
  62.   vector<int>::iterator setWalker2 = uniSet.end();
  63.   while(setWalker1 != uniSet.begin() + i - 1 ){
  64.     set1.push_back(*setWalker1);
  65.     ++setWalker1;
  66.   }
  67.   setWalker2 = setWalker1;
  68.  
  69.   while(setWalker2 != uniSet.end() - i + 1){
  70.     ++setWalker2;
  71.   }
  72.   //random_shuffle(setWalker1, setWalker2);
  73.   int siA = int((setWalker2-setWalker1)*proportion);
  74.  
  75.   for(int j = 0; j < siA; ++j){
  76.     set1.push_back(*setWalker1);
  77.     ++setWalker1;
  78.   }
  79.   while(setWalker1 != setWalker2){
  80.     set2.push_back(*setWalker1);
  81.     ++setWalker1;
  82.   }
  83.   while(setWalker1 != uniSet.end()){
  84.     set2.push_back(*setWalker1);
  85.     ++setWalker1;
  86.   }
  87.   //random_shuffle(set1.begin(), set1.end());
  88.   //random_shuffle(set2.begin(), set2.end());
  89.  
  90.  
  91. }
  92.  
  93.  
  94.  
  95. vector<int>::iterator binary_search_iterated(vector<int>* arr, vector<int>::iterator low, vector<int>::iterator high, int x){
  96.     if (high >= low){
  97.         vector<int>::iterator mid = low + (high - low)/2;
  98.  
  99.         if (*mid == x){
  100.             return mid;
  101.         }
  102.         else{
  103.             if (*mid > x){
  104.                 return binary_search_iterated(arr, low, mid - 1, x);
  105.             }
  106.             else{
  107.                 return binary_search_iterated(arr, mid + 1, high, x);
  108.             }
  109.         }
  110.  
  111.     }
  112.     else{
  113.         return low;
  114.     }
  115.  
  116. }
  117.  
  118.  
  119.  
  120. void BaezaYates_step(vector<int>* A, vector<int>* B, vector<int>::iterator A_begin, vector<int>::iterator A_end, vector<int>::iterator B_begin, vector<int>::iterator B_end, unordered_set<int> *C, int i = 0){
  121.  
  122.     if (A_end - A_begin <= 0 || B_end - B_begin <= 0){
  123.         return;
  124.     }
  125.     vector<int>::iterator midB = B_begin + (B_end - B_begin)/2;
  126.     int midBval = *midB;
  127.     vector<int>::iterator midA = binary_search_iterated(A, A_begin, A_end, midBval);
  128.     vector<int>::iterator a_res,b_res;
  129.     cout <<i<<endl;
  130.     if ((midA-A_begin) > (midB-B_begin)){
  131.         cout << A_end - A_begin << endl << B_end - B_begin;
  132.        
  133.         cout<<endl;
  134.  
  135.         BaezaYates_step(A,B,A_begin, midA, B_begin, midB, C, i+1);
  136.     }
  137.     else{
  138.       cout << A_end - A_begin << endl << B_end - B_begin;
  139.      
  140.        
  141.         cout<<endl;
  142.         BaezaYates_step(B,A,B_begin, midB, A_begin, midA, C, i+1);
  143.     }
  144.     if (*midA == midBval){
  145.         cout << "Inserted\n\n\n";
  146.         C->insert(midBval);
  147.     }
  148.     if ((A_end - midA) > (B_end - midB)){
  149.       cout << A_end - A_begin << endl << B_end - B_begin;
  150.  
  151.         cout<<endl;
  152.         BaezaYates_step(A,B,midA+1, A_end, midB+1, B_end, C, i+1);
  153.     }
  154.     else{
  155.       cout << A_end - A_begin << endl << B_end - B_begin;
  156.  
  157.         cout<<endl;
  158.         BaezaYates_step(B,A,midB+1, B_end, midA+1, A_end, C, i+1);
  159.     }
  160.    
  161. }
  162.  
  163. int main(){
  164.  
  165.   int res[3];
  166.   vector<int> lcg_res;
  167.  
  168.   coefficient_gen(res, 14);
  169.  
  170.   cout << res[0] << ' ' << res[1] << ' ' << res[2] << endl;
  171.   vector<int>  s1;
  172.   vector<int>  s2;
  173.  
  174.   generate(s1, s2, 14,30000,0.8, 1);
  175.  
  176.   cout << s1.size() << ' ' << s2.size() << endl;
  177.  
  178.   unordered_set<int> c;
  179.  
  180.   //BaezaYates_step(s1, s2, s1.begin(), s1.end(), s2.begin(), s2.end(), &c);
  181.  
  182.   return 0;
  183. }
RAW Paste Data