Random numbers: No repeats

[NerdTastic]

I'm attempting to fill an array of size 200 with random numbers between 1 and 1000 but I can have no repeats, and the way I'm currently doing it gives me an infinite loop, I'm assuming because it detects repeats so much. is there a better way than this, or an algorithm you could recommend, that will accomplish this better?

//within main

    srand(time(NULL));

	x=0;
	cout << x;
	

	do
	{
		numbers[x]=rand() % 1000+1;
		cout << numbers[x] << endl; //debug
		y=0;

		do
		{

			if(numbers[x]==numbers[y])
			{x--; break;}

			y++;
			cout << numbers[x] << endl; //debug

		}while(y<(x-1));

		x++;
	}while(x<200);

EDIT: The debug statements were for me to see if any values were being assigned. My breakpoints never did anything for some reason.

[Peter87]

If you change the inner loop to a while loop it will work better.

[NerdTastic]

Why is that?

[Peter87]

Think about what happens on the first iteration.

[NerdTastic]

so the first iteration is ALWAYS going to flag the inner loop?

[Peter87]

It depends on what you mean by "flag".

[MrHutch]

Take a look at what value x has. Take a look at what value y has. In the first iteration.

Now look at that if statement.....

[NerdTastic]

The first check will always be numbers[0]==numbers[0] and will always break the loop, returning to the initialization of numbers[0] which will (again) equal numbers[0], and so on. Ahhhhh.

So, why would a while loop correct that?
Edit: Would it be better to compare to y-1?

[Peter87]

Do you know the difference between a while and do-while loop?

Edit: Would it be better to compare to y-1?

No

[NerdTastic]

While checks the loop condition before executing, and do-while checks the loop condition after executing, correct?

[JLBorges]

> fill an array of size 200 with random numbers between 1 and 1000 but I can have no repeats

One way to do this in linear time is:
a. create a sequence of 1000 numbers [1,2,3,...,1000].
b. shuffle the sequence randomly.
c. pick up the first 200 numbers.

for example:

enum { N = 200, M = 1000 } ;

std::vector<int> seq(M) ;
std::iota( seq.begin(), seq.end(), 1 ) ;

std::random_device rand_dev ;
std::mt19937 twister( rand_dev() ) ;
std::shuffle( seq.begin(), seq.end(), twister ) ;

seq.resize(N) ;

[Disch]

or you could use a set?

std::set<int> nums;

while(nums.size() < 200)
{
  nums.insert( rand() % 1000 );
}

int array[200];
std::copy( nums.begin(), nums.end(), array );
std::random_shuffle( array, array + 200 );

[Peter87]

I see now that the loop condition should actually be y<x.

If you use the while loop it will not enter the inner loop because y<x is false when x and y equals zero.

[Stewbond]

JLBorges,

It took me a while to find std::random_device and std::mt19937, but what is std::shuffle and which header is it in?

[Albatross]

Stewbond,
I think JLBorges was referring to random_shuffle, which is in the <algorithm>
header.

http://cplusplus.com/reference/algorithm/random_shuffle/

random_shuffle takes two iterators, one pointing to the beginning of your array and one pointing to the end (pointers to elements of an array count as iterators), and optionally a function that can be used to generate random numbers to determine which elements should be shuffled.

-Albatross

[cire]

std::shuffle was introduced with the latest standard.

http://en.cppreference.com/w/cpp/algorithm/random_shuffle

[Albatross]

Oh, okay. I see. Thanks for letting me know!

-Albatross

[NerdTastic]

I tried using JLBorges solution (though mine is somewhat simpler looking, I think) and got an error. Here's the code

#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include <vector>
#include <algorithm>

using std::vector;

std::vector<int> Num_Array;
int x, y, z;


void main()
{
	
srand(unsigned(time(NULL)));
	
	x=0;

	for(x=0; x<1001; x++) Num_Array.push_back(x);

	random_shuffle(Num_Array.begin(), Num_Array.end());

	for(x=0; x<201; x++) cout << Num_Array[x] << '\t';

}

g:\c++\2004_four_two\2004_four_two.cpp(22) : error C2065: 'random_shuffle' : undeclared identifier

I was under the impression that random_shuffle was contained in algorithm.h

I know that my headers have .h, that's because I have to use an ancient compiler, Vc++ 6.0 Enterprise

[JLBorges]

//random_shuffle(Num_Array.begin(), Num_Array.end());
std::random_shuffle(Num_Array.begin(), Num_Array.end());

[NerdTastic]

Thank you! Works now:)