Created
August 9, 2023 05:46
-
-
Save Vicfred/49a4fec3348bbb617b96c37bd14b9206 to your computer and use it in GitHub Desktop.
Coupon collector problem
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://math.stackexchange.com/questions/28905/expected-time-to-roll-all-1-through-6-on-a-die | |
// https://en.wikipedia.org/wiki/Coupon_collector%27s_problem | |
#include <iostream> | |
#include <random> | |
#include <set> | |
using namespace std; | |
int main() { | |
long double expected = 0.0L; | |
const long long int MAXN = 1e5; | |
const long long int howmany = 200; | |
random_device rd; | |
mt19937 gen(rd()); | |
uniform_int_distribution<> dis(1, howmany); | |
for (int i = 0; i < MAXN; ++i) { | |
long long trials = 0LL; | |
set<int> numbers; | |
while (numbers.size() < howmany) { | |
numbers.insert(dis(gen)); | |
trials += 1LL; | |
} | |
expected += (long double) trials; | |
} | |
cout << (long double)(expected/MAXN) << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment