Unique random integers

[highwayman]

Is there a way to generate unique random numbers using the <random> header?

  int a = std::uniquePRNG();

[lastchance]

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.

[Duthomhas]

Some time ago JLBorges posted a nice algorithm to do just this. I'll try to look it up when I get home to ight.

[George P]

Is there a way to generate unique random numbers using the <random> header?

The answer and the code hinges on what you mean by "unique numbers."

lastchance has a great suggestion if you want no duplicated numbers in your series.

[highwayman]

@everyone: sorry about disappearing for so long

@lastchance: thanks, that sounds perfect, I had forgotten sets were a thing would have never crossed my mind xp

@Duthomhas: Oh, cool that would also work, always nice to have something made by a more experienced person than me.

@Furry Guy: yeah, I just meant no duplicated numbers. What are the other meanings? How are there other meanings?

[Duthomhas]

Hey, JSYK I did’t forget this. My Google-fu is just not strong enough to fish this particular rabbit out of the hat.

Sorry.

[JLBorges]

Was it this one (Knuth's algorithm S)? http://www.cplusplus.com/forum/general/241432/#msg1073612

[highwayman]

@Duthomas Thanks anyway.

@JLBorges thanks

[Duthomhas]

@JLBorges
Yes! That’s it.
I was kind of hoping you would notice this thread and be able to find it.

My google searches did not include the word “repetitive”, but I swear I used every combination of all the other words in that title... LOL.

[adam2016]

I like the idea of sets, great answer :)

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.

[jonnin]

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.

[adam2016]

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.

that's actually a great idea.

[helios]

for (int i = 0; ; i++)
    std::cout << rjindael(i, random_key) << std::endl;

Guaranteed to generate a unique series of non-repeating 128-bit integers.

[adam2016]

execution time on average - 0.183 seconds

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.

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;

vector<int> numbers;
bool firstTime = true;

void populateVector(){

    bool unique = false;
    int number;

    if(firstTime){

        number =  1 + rand() % 100;
        numbers.push_back(number);
        firstTime = false;
        return;
    }

    while(!unique){

    number =  1 + rand() % 100;

    for(int i = 0; i < numbers.size(); ++i){

        if(number == numbers.at(i)){

            break;
        }
        if(i == numbers.size()-1){

            unique = true;
        }
      }
    }
    numbers.push_back(number);
}

int main()
{
   srand(time(NULL));

   for(int i = 0; i < 99; ++i){

      populateVector(); // populate the vector with random numbers
   }

   for(int i = 0; i < 99; ++i){

      cout <<  "number " << i+1 << " = " << numbers.at(i) << endl;
   }
    return 0;
}

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

[George P]

#include <iostream>
#include <chrono>
#include <random>
#include <unordered_set>
#include <functional>
#include <set>

int main()
{
   // set minumum and maximum values
   const unsigned MIN { 0 };
   const unsigned 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;

   const unsigned 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 (const auto& 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 (const auto& itr : sorted_pack)
   {
      std::cout << itr << '\t';
      count++;

      if (0 == count % 10)
      {
         std::cout << '\n';
         count = 0;
      }
   }
   std::cout << '\n';
}

There are 50 random numbers:
86      5       23      87      39      2       66      17      41      16
76      75      89      25      33      21      55      79      15      4
68      20      73      95      13      44      26      27      74      10
6       70      37      47      14      40      94      7       3       67
29      8       46      45      58      92      18      99      49      1


The numbers sorted:
1       2       3       4       5       6       7       8       10      13
14      15      16      17      18      20      21      23      25      26
27      29      33      37      39      40      41      44      45      46
47      49      55      58      66      67      68      70      73      74
75      76      79      86      87      89      92      94      95      99

[helios]

adam2016: Now do it with 10000 numbers.

[adam2016]

^^ I was hoping no one would say that lol

very true, I like last chance's second method -

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)

[E8A4Nwbp]

This is SIMILAR to my need! Quite the happenstance!

this is my code:

X.push_back(Vec2(visibleSize.width / 4 + origin.x, visibleSize.height / -0.63 + origin.y));
	X.push_back(Vec2(visibleSize.width / 4 + origin.x, visibleSize.height / -0.67 + origin.y));
	X.push_back(Vec2(visibleSize.width / 4 + origin.x, visibleSize.height / -0.61 + origin.y));
	X.push_back(Vec2(visibleSize.width / 4 + origin.x, visibleSize.height / -0.58 + origin.y));
	X.push_back(Vec2(visibleSize.width / 4 + origin.x, visibleSize.height / -0.55 + origin.y));

	for (int i = 0;i<8;i++)
	{
		auto NimCounters = Sprite::create("PaperclipG.png"); 
		NimCounters->setPosition(X[rand() % X.size()]);
		NimCounters->setScale(visibleSize.width / 1400, visibleSize.height / 1200);
	    this->addChild(NimCounters);
	}

How can I ensure this line
NimCounters->setPosition(X[rand() % X.size()]);
is always unique?

[jonnin]

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.

[Duthomhas]

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.

_{^{Hmm... jonnin gave me an idea...}}