Printable View
If I have a piece of working as per below:
How do I find doubles generated by the second loop?Code:default_random_engine engine
{
static_cast<unsigned int>(time(0))
};
uniform_int_distribution<unsigned int> randomInt{ 1, 500 };
for (int i = 1; i < 100; i++) //first loop
{
for (int j = 1; j < 50; j++) //second loop
{
cout << randomInt(engine) << " ";
}
cout << endl;
}
What you mean by 'find doubles'? Can you give an example.
Maybe you mean duplicates? Do you want to avoid them? One method is to add each new random number to an std::vector after making sure it is not already in there. Another method is to add the random numbers to a data structure that rejects duplicates, for example, an std::set or an std:: unordered_set. This is fast but the random order of the random numbers gets lost. It can be fixed using std::random_shuffle.Quote:
Originally Posted by rockz
Note that for your first loop to iterate 100 times and the second 50 times, either the loop variables must start at 0, or the < signs must be <=.
Yes duplicates. I don't want to avoid them, but I want set a counter variable to determine how many duplicates are generated.Quote:
Originally Posted by wolle
Then I suggest you use an std::unordered_set,Quote:
Originally Posted by rockz
https://en.cppreference.com/w/cpp/co.../unordered_set
You insert each new random integer into the unordered_set using the insert function. You can detect duplicates in two ways. Either you check the return value of insert. If it indicates a reject, you know the random number is a duplicate. Or you use the contains function before the insert function to check whether the random number is already there. If it is, it is a duplicate.
Another more indirect way is to just insert all random numbers into the unordered_set. Say you insert 50 random numbers. Afterwards, you check how many have actually been inserted using the size function. If it says 48 you know there were 2 duplicates.
I'm actually doing this for demonstration purpose. I need to collect statistics from the output. So my question is, can it be possible to allow the method to run and then traverse through to find out if there are duplicates? And if there are any duplicates (or even triplicates), have a counter variable to update on the number of instances. I know it can be easily achieved using arrays, but I'm trying my best to avoid arrays. I would like to employ as much features as possible from C++11 and beyond.
Duplicity is a relative property between two entities. To compare the current entitity in a sequence with previous entities, one must store them somewhere. Unless, of course, duplicity is an intrinsic property of the entities. In that case, each entity knows it will appear X times in the course of the next N entities of the sequence. That is possible to achieve with computer-generated random numbers because they are deterministic. I am, however, not aware of any standard random number generator that offers this property. It would go against the independence rule stating that the current number should have no relation to previous numbers.Quote:
Originally Posted by rockz
There seems to be a theoretical divide here. Either duplicity is intrinsic to your entities, or you need to store them.
As a possible starter, perhaps:
Code:#include <random>
#include <unordered_set>
#include <iostream>
std::mt19937 engine {std::random_device {}()};
int main() {
constexpr unsigned l1sze {100};
constexpr unsigned l2sze {50};
std::uniform_int_distribution<unsigned> randomInt {1, 500};
std::unordered_set<unsigned> nos;
unsigned nodup {};
for (int i = 1; i < l1sze; ++i)
for (int j = 1; j < l2sze; ++j)
nodup += !nos.insert(randomInt(engine)).second;
std::cout << "There were " << nodup << " duplicate numbers\n";
}
Say you draw numbers at random from a range of equally likely numbers. At some point, all numbers have come up at least once. After that, all drawn numbers will be duplicates. With N numbers in the range, that happens after approximately N * ln(N) drawn numbers. See the Coupon collector's problem,Quote:
Originally Posted by rockz
https://en.wikipedia.org/wiki/Coupon...or%27s_problem
In your example code, the random range contains N=500 numbers. So after approximately 500 * ln(500) = 3107 drawn numbers on average, all 500 numbers have come up at least once. That is a kind of saturation point or phase shift. From then on, the number of duplicates is not random but deterministic. It is the number of drawn numbers minus the size of the random number range. In your example code, (100-1)*(50-1) = 4851 random numbers are drawn. It exceeds the phase shift point of 3107 with some margin. It means the phase shift is quite likely to take place. And this explains why 2kaud's code very often ends up with 4851-500 = 4351 duplicates.
My point is that it does not hurt to be aware of the N*ln(N) phase shift when collecting statistics about duplicates. If it continues beyond the phase shift you do not need a simulation to learn the result. It is known beforehand.
You could use a std::map<unsigned int, int> with the key the generated number and the value the occurence counter like in this example:
https://en.cppreference.com/w/cpp/numeric/random
Thanks for the kind words, really appreciate it. My analogy is not as discussed in the coupoun problem but more of in the Birthday problem, So calculating the probability of finding a double in individual set over mulitple iterations.Quote:
Originally Posted by wolle
Mathematically it's 50.7% at a size of 23, but i would like to experiment computationally.
I posted a solution strategy to this problem quite some time ago now,Quote:
Originally Posted by rockz
https://forums.codeguru.com/showthre...rthday+problem
Today, I can just barely understand my post, but it seems to involve hashing :).
Oh wow!!!. Just Wow!!Quote:
Originally Posted by wolle
I don't know if anyone managed to solve the problem, but I found a solution done in Pyton on YT. According to the creator of the video, after a 1000 runs, there is a probablity of >50% that there will be a double in each transaction. I found it to be inexact, so I thought to re-code it in cpp.
I know if I dumped all the data into a <map> it will give me the results I expect, but using <map> may not be the optimal way to achieve the results, minimizing the complexities.