# 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