I'm not convinced that they are truly random if you force them to be unique.
However ...
Method 1: put the "random" numbers in a std::set until that set has the desired size N; (c++ sets don't permit duplicates).
Method 2 (moderate range of integers): put the full range of distinct integers in a container and std::shuffle the contents. Then take (e.g.) the first N.
I was going to say , add each random number to a vector and compare the random number generated to each number in the vector if the number equals a number in the vector, create a new random number, repeat until you've found a unique number.
Again using sets sounds better but that's my half baked solution.
your solution works pretty well if the number of numbers is small AND the % of consumed numbers from the set is not much over half.
consider 1-10, and you want all 10 numbers:
you randomly get 1,2,3,4,5,6,7 ... ok, now you start to see issues, you roll 1, search for it, already used, you roll 5, search for it, already used, you roll 3, search, used, 1 comes up again, then 2, and then 9... finally, a new one... the last number, if you wanted one copy of each value, could spend quite some time trying to get the final value randomly because almost everything is used. extrapolate that, say you wanted a million numbers... getting the last one could actually take many seconds to find, or worse! the set /shuffle type idea gets that last number just as fast as the first one: its just the next one in line...
if you only want 500k numbers out of a million, at least you have a 50/50 chance every re-try to get one... etc
or, to sum it up: been there, done that, and learned from my mistake! Even when this idea works, its not that much harder to code one of the better above ideas that always works. You get absolutely nothing from doing it this way, and its high risk of bad performance.
Very good point especially as you said if you are looking for a number from 1 to 10 and already have 7-8 numbers, finding the next unique number could take some time.
Method 2 (moderate range of integers): put the full range of distinct integers in a container and std::shuffle the contents. Then take (e.g.) the first N.
note code is ugly and "using std" or globals is never a good idea but this is just for illustration and probably a lot better ways of doing it ( love to hear them ) but 0.183 seconds ins't that bad on average , in this example I have generated 99 random numbers from 1 to 100, I thought on average this would take a couple of seconds ( and maybe it could ) but the average time was relative quick.
number 1 = 26
number 2 = 74
number 3 = 95
number 4 = 67
number 5 = 13
number 6 = 19
number 7 = 48
number 8 = 46
number 9 = 62
number 10 = 23
number 11 = 8
number 12 = 18
number 13 = 57
number 14 = 58
number 15 = 6
number 16 = 7
number 17 = 54
number 18 = 78
number 19 = 77
number 20 = 21
number 21 = 24
number 22 = 86
number 23 = 38
number 24 = 41
number 25 = 83
number 26 = 80
number 27 = 9
number 28 = 50
number 29 = 92
number 30 = 94
number 31 = 34
number 32 = 87
number 33 = 60
number 34 = 15
number 35 = 14
number 36 = 76
number 37 = 56
number 38 = 72
number 39 = 65
number 40 = 93
number 41 = 29
number 42 = 30
number 43 = 5
number 44 = 96
number 45 = 11
number 46 = 4
number 47 = 97
number 48 = 89
number 49 = 45
number 50 = 69
number 51 = 49
number 52 = 63
number 53 = 51
number 54 = 59
number 55 = 44
number 56 = 10
number 57 = 55
number 58 = 17
number 59 = 25
number 60 = 1
number 61 = 99
number 62 = 33
number 63 = 37
number 64 = 43
number 65 = 68
number 66 = 35
number 67 = 12
number 68 = 100
number 69 = 39
number 70 = 2
number 71 = 66
number 72 = 75
number 73 = 81
number 74 = 40
number 75 = 98
number 76 = 64
number 77 = 90
number 78 = 32
number 79 = 3
number 80 = 31
number 81 = 79
number 82 = 53
number 83 = 47
number 84 = 16
number 85 = 28
number 86 = 20
number 87 = 36
number 88 = 71
number 89 = 22
number 90 = 61
number 91 = 85
number 92 = 84
number 93 = 88
number 94 = 91
number 95 = 82
number 96 = 42
number 97 = 70
number 98 = 73
number 99 = 52
#include <iostream>
#include <chrono>
#include <random>
#include <unordered_set>
#include <functional>
#include <set>
int main()
{
// set minumum and maximum values
constunsigned MIN { 0 };
constunsigned MAX { 99 };
// obtain a seed from the system clock:
unsigned seed =
static_cast<unsigned> (std::chrono::system_clock::now().time_since_epoch().count());
// create a random engine, using the time seed
std::default_random_engine rng(seed);
// create a distribution from MIN to MAX, inclusive
std::uniform_int_distribution<unsigned> dis(MIN, MAX);
// create an alias for generating a random number
auto roll = std::bind(dis, rng);
// create an unordered_set, so the generated random numbers are not sorted
std::unordered_set<unsigned> pack;
constunsigned num_rolls { 50 };
while (pack.size() < num_rolls)
{
// try to get the new random number at the end of the unordered set
pack.emplace_hint(pack.end(), roll());
// without the functional binding
// pack.emplace_hint(pack.end(), dis(rng));
}
std::cout << "There are " << pack.size() << " random numbers:\n";
unsigned count { };
for (constauto& itr : pack)
{
std::cout << itr << '\t';
count++;
if (0 == count % 10)
{
std::cout << '\n';
count = 0;
}
}
std::cout << "\n\n";
std::set<unsigned> sorted_pack;
sorted_pack.insert(pack.begin(), pack.end());
std::cout << "The numbers sorted:\n";
count = 0;
for (constauto& itr : sorted_pack)
{
std::cout << itr << '\t';
count++;
if (0 == count % 10)
{
std::cout << '\n';
count = 0;
}
}
std::cout << '\n';
}
Method 2 (moderate range of integers): put the full range of distinct integers in a container and std::shuffle the contents. Then take (e.g.) the first N.
but doesn't std::shuffle itself not use a PRG to actually shuffle the contents( ie choosing index's at random)
but doesn't std::shuffle itself not use a PRG to actually shuffle the contents( ie choosing index's at random)
yes. But it *ensures* that the container is shuffled. Then when you iterate the container, because it contains the numbers you wanted, you only get those numbers back in some random order. If the shuffle itself hits the same index more than once, no harm done. I always thought shuffle was kind of an extra: you can make a nonsense sort comparison to shuffle, even going so far as to use <random> to decide the compare.
Just to be pedantic about the double negatives here*: std::shuffle does use a PRNG. (You must supply it as argument.)
jonnin correctly deciphered this and gave a good answer: the shuffle algorithm is a pretty sweet piece of engineering; I would be surprised if any implementations existed that didn’t use the Knuth Fisher Yates algorithm.
*Double negatives are not a thing in English, and when they do appear you need a whole lot of context to understand whether the statement is actually affirmative or negative.