Generating random numbers from 0-n

[PaulProgramer]

Hello, I have a problem with my program that I can´t figure out. I would appreciate if someone could give me some hints on what to do.
I am trying to write a program that checks how many random numbers less than a positive integer N one should generate before all integer values between 0 and N are produced at least once.

The code that I give here is not all of the code that I have. I have added a function that sorts the array in a ascending order from lowest to highest, so you can assume that the array is sorted.

What I need is for the program to loop until all the numbers from 0 -n have come up in the array at least once. So far it doesn´t loop automatically. I have tried to use a do while loop without success and manually loop it with cout<<"Do you want to try again?; But if I do that the program doesn´t remember what numbers have already come up in the array. Say if the first time I run the random numbers function for n=4 the numbers that come up are 0233, then I want to be able to run it again until the numbers 1 has come up.
Thank you.

//void selectionSort(int arr[], int size); For sorting the array
int main()
{
    int n,isTrue=1;
    cout<<"Put in the number: "<<endl;
    cin>>n;
    cout<<"There are: "<<n<<" elements in the array. "<<endl;
   //To generate random numbers
    srand((unsigned)time(0));

    while(isTrue!=0){ // to generate a loop that will continue until all the elements in the array have appeared
    int counter=0;
    counter++;
    int arr[n];
    cout << "The numbers are: "<<endl;
    for(int i=0; i<n; i++)
    {
    arr[i] = (rand()%n);
    cout << arr[i]<<" ";
    }
    selectionSort(arr, n); // this sorts the array in ascending order from 0-N

	int s,j;
    for(s = 0; s < n && isTrue == 1; s++)
    {
        for( j = s+1; j < n; j++)
    {
        if( arr[s] >= arr[j] )
       {
             isTrue = 0;
             cout<< ""<<endl;
             cout<< "Not all of the numbers from 0-n came up!"<<endl;
        }
    }
    }
}
    return 0;

}

[Chilton]

You could use an associative container, such as a map, that has unique key values (in your case integers). The container is self-ordering, so by testing the difference between each successive key value (integer), you can find out which integer you'd need to search for next if their difference isn't 1.

[Narue]

You could use an associative container, such as a map, that has unique key values (in your case integers).

Unless N is likely to be very large (I wouldn't bet on it), the brute force approach would be simpler and probably more efficient:

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

int main()
{
    std::srand((unsigned)std::time(nullptr));
    
    int n;
    
    std::cout << "Enter N: ";
    
    if (std::cin >> n) {
        std::vector<int> v(n);
        
        while (std::any_of(v.begin(), v.end(), [](int x) { return x == 0; }))
            ++v[std::rand() % n];
            
        for (std::vector<int>::size_type i = 0; i < v.size(); i++)
            std::cout << i << ": " << v[i] << '\n';
    }
}

Of course, this is given my reading of the requirements which suggests that the OP wants to display the random number generator's distribution pattern.

[WaltP]

I'd do something a little more 'noobie' (starting from Narue's code):

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

int main()
{
    int  n;
    int  val;
    int  array[MaxSize];
    bool done;

    for (n=0; n<MaxSize; n++) array[n] = 0;
    srand((unsigned)time(nullptr));
    
    cout << "Enter N: ";
    if (cin >> n) 
    {
        done = false;
        while (done)
        {
            array[rand() % n]++;
            for (val = 0; val < n; val++)
            { 
                if (array[val] == 0) break;
            }
            if (val >= n) done = true;
        }
        // display what you want...
    }
}

At the end, array[] will contain the number of times each random value was generated. Add them up and you get the number of time rand() was called.

Keep in mind the technique of calling rand() until all numbers are generated could never end. There's no guarantee that all numbers will be generated -- as per definition of random.

My reason for using the noob technique is most early students have no idea what a vector is nor the algorithm package.

[Narue]

My reason for using the noob technique is most early students have no idea what a vector is nor the algorithm package.

Funny, that's my reason for not using the noob technique. ;)

[PaulProgramer]

Hey guys, thanks for all your answers. I will look into this. Highly appreciated.