Generate non-repetitive random numbers without arrays

[applj]

I'm fairly new to c++ and I'm making a random number generator program.

Update:
I've already solved the generator part but the program requires that the random numbers must never repeat. I'm not sure how to do that without arrays so i would prefer simple looping if possible. Any help is greatly appreciated! Here's what I have so far:

#include <iostream> 
#include <cstdlib>
#include <ctime>
#include <Windows.h>


using namespace std;

class Numbers {
private: int rndNum, howmany, ctr, even, odd;
		 char repeat;
public:  void GenerateRandNum();
};

void Numbers::GenerateRandNum()
{
	do {
		cout << "How many random numbers would you like to generate (1-100)? ";
		cin >> howmany;
		cout << endl << " The " << howmany << " random numbers are: " << endl;

		srand(time(0));
		for (ctr = 1; ctr <= howmany; ctr++)
		{
			rndNum = rand() % 100 + 1;
			cout << rndNum << "\t";

			if (rndNum % 2 == 0)
			{
				even++;
				cout << "Even Numbers: " << even << endl;

			}
			else
			{
				odd++;
				cout << "Odd Numbers: " << odd << endl;
			}

			cout << endl << "Press [Y/y] to continue." << endl;
			cin >> repeat;
			repeat = toupper(repeat);
		}

		while (repeat == 'Y');
	}
}
	
	int main()
{
	Numbers obj;
	obj.GenerateRandNum();
	system("pause");
	return 0;
}

[keskiverto]

Do not doublepost. The other thread: http://www.cplusplus.com/forum/beginner/241426/

[Duthomhas]

You can't guarantee no repeats without some kind of storage.

For a small collection of random values, just use an array that has been randomized.
For a larger collection, use a Bloom filter (https://www.google.com/search?q=bloom+filter+c%2B%2B) or Hash set (http://www.cplusplus.com/reference/unordered_set/unordered_set/).

Good luck!

[SamuelAdams]

You can't guarantee no repeats without some kind of storage.

You can simply by making sure the next number is larger, until you run out of possible numbers. Yes I know that's not truly random....

[ne555]

it is as random as not doing it
it may not be uniform or normal, however.

[Duthomhas]

No, it is a completely different thing. A non-decreasing sequence is not random, even if the distance between successive terms is random.

A way to think of it is this: Given a bag with the numbers 0..9 in it, how likely is it that the very first number I pull is '0'?

For a truly random pull the answer is 1/10.
This is called “uniform” — meaning that the probability of getting pulled is the same for every number, every single time you pull one.

If we want something non-uniform but still random, all we need to do is play with the probabilities. For example, I can say that the probability I pull a '0' for the first number should be 9/10. That makes it nearly certain that I will get a '0' on my first pull, but not guaranteed.

Once the probability is set to 10/10 it is no longer random. It is the opposite of random — it is definite or fixed.

Therein lies the problem with a non-decreasing sequence. Suppose I pull a '7' for my first number? It is now impossible to pull the numbers '0'..'6' (since they're strictly less than seven). That leaves us with nine pulls remaining but only three possible answers. Do you see what happened? The probability of pulling a '0'..'6' is now 0/10 — again not random. (c.f The Monty Hall problem, for those of you wanting more reading.)

There is a whole lot more to it, but I’ll leave it at that for now.

[JLBorges]

From 'The Art of Computer Programming, Volume 2: Seminumerical Algorithms' by Knuth

Algorithm S (Selection sampling technique). To select n records at random from a set of N, where 0 < n ≤ N.

S1. [Initialize.] Set t ← 0, m ← 0. (During this algorithm, m represents the number of records selected so far,
and t is the total number of input records that we have dealt with.)

S2. [Generate U.] Generate a random number U, uniformly distributed between zero and one.

S3. [Test.] If (N – t)U ≥ n – m, go to step S5.

S4. [Select.] Select the next record for the sample, and increase m and t by 1. If m < n, go to step S2;
otherwise the sample is complete and the algorithm terminates.

S5. [Skip.] Skip the next record (do not include it in the sample), increase t by 1, and go back to step S2.

Verbatim implementation in C++:

#include <iostream>
#include <random>

// select and print n unique numbers chosen at random from [1,N]. invariant: n <= N
void select_and_print( std::size_t n, std::size_t N )
{
    static std::mt19937 rng( std::random_device{}() ) ;
    int next_number = 0 ;
    double U ;

    // S1: // [Initialize.]
        // Set t ← 0, m ← 0. (During this algorithm, m represents the number of records selected so far,
        // and t is the total number of input records that we have dealt with.)
        std::size_t t = 0, m = 0 ;

    S2: // [Generate U]
        // Generate a random number U, uniformly distributed between zero and one.
        U = std::generate_canonical<double,64>(rng) ;

    // S3: // [Test.]
        // If (N – t)U ≥ n – m, go to step S5.
        if( (N-t)*U >= (n-m) ) goto S5 ;

    // S4: // [Select.]
        // Select the next record for the sample, and increase m and t by 1.
        std::cout << m+1 << ". " << ++next_number << '\n' ;
        ++m ;
        ++t ;
        // If m < n, go to step S2; otherwise the sample is complete and the algorithm terminates.
        if( m < n ) goto S2 ;
        else return ;

     S5: // [Skip.]
        // Skip the next record (do not include it in the sample),
        ++next_number ;
        // increase t by 1, and go back to step S2.
        ++t ;
        goto S2 ;
}

int main()
{
    select_and_print( 15, 100 ) ;
}

http://coliru.stacked-crooked.com/a/4a9b3f461a334683
http://rextester.com/FAT24576

TO DO: rewrite in idiomatic C++ (use a while loop etc.)

[Repeater]

From 'The Art of Computer Programming, Volume 2: Seminumerical Algorithms' by Knuth

Yikes. Someone got the big guns out!

[lastchance]

JLBorges wrote:

TO DO: rewrite in idiomatic C++ (use a while loop etc.)

#include <iostream>
#include <random>
#include <chrono>
using namespace std;

int main()
{
   unsigned seed = chrono::system_clock::now().time_since_epoch().count();
   mt19937 gen( seed );
   uniform_real_distribution<double> dist( 0.0, 1.0 );
   const int n = 100, r = 15;                              // Random selection of r distinct numbers in 1...n
   
   int available = n, required = r;
   int number = 0;

   while ( required )
   {
      number++;
      double probability = (double)required / available;   // Probability that this one is selected
      double p = dist( gen );
      if ( p < probability )                               // Yeah, select it!
      {
         cout << number << " ";
         required--;
      }
      available--;
   }
}

Could reduce the number of variables, since number+available=constant; however, it's then harder to see what is going on.

[jonnin]

not sure how to do that without arrays so i would prefer simple looping if possible.

maybe should just show him how to do it with arrays?

The naive way (better approach below).
1) make an array of boolean over your range. say you want 1000 to 2000, you can either make an array of 2001 or 1000 and adjust. Lets do 1000 adjusted to be efficient
2) roll a number in your range. check array[index], if false, proceed, if true, reroll.
say you rolled 1500. then you want to set array[500], which is 1500- lowval_in_range or 1500-1000 here, or in code array[value-lowval] = true; (to set it, to check it its == of course).
2.b once index is false, set array[index] to true.
3) use the number.
goto 1.

this begins to fail if you try to pick more than some % of the values. Imagine you want every single value in a large range and there is only 1 left, it could take seconds or even mins to finally roll the last unused value. Here say 1500 was the only unused value... roll, 1321? nope, used. 1843? Nope, used. ... after rerolling a billion times it finally hits 1500.... ugg.

the better approach:
int array[how many numbers];
for(...) fill in array with all the possible values (they don't have to be sequential, they could be the fibonacchi numbers or the digits of pi or 1-1000. Doesn't matter, but if you want distinct you can only load each value 1 time for this algorithm. If you want a distribution, you can repeat some values multiple times (eg normal would repeat 1 many times but the middle value 1 time and between them less and less as you get to the middle from both ends etc. get a correct equation from statistics book/web/etc for this distribution stuff!).
shuffle the array (there are built in <algorithm> for this).
iterate and select: take array[0], use it, take array[1], use it, ... until you have consumed all values. Because of the shuffle, this makes the iterated choice random, and because of the iteration, each value is only consumed once (assuming it is distinct in the array, of course).

both approaches work. the first one is inferior but you see people doing stuff like that for simple problems.