Program works only if I keep displaying something until solution is found

Question

I have made a program that generates a random array of numbers. I am aware that if I make a for structure to place random numbers, there might be a chance that I will have values that will repeat. For that I made a separate recursive function that keeps looking for duplicates and replace them with other values until there will be only distinct numbers:

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
int n, m, k, row[100];
int verif(int v[100], int k)
{
    for(int i=0; i<k-1; i++)
        for(int j=i+1; j<k; j++)
            if(v[i]==v[j])
            {
                cout<<".";
                srand(time(NULL));
                v[i]=rand()%100+1;
                return verif(v, k);
            }
             return 1;
}
int main()
{
    k=10, n=10;
    srand(time(NULL));
    row[0]=rand()%n+1;
    srand(row[0]);
    for(int i=1; i<k; i++)
    {
        srand(row[i-1]);
        row[i]=rand()%n+1;
    }
    verif(row, k);
     for(int i=0; i<k; i++)
        cout<<row[i]<<" ";
    return 0;
}

I hope you can explain me why does a simple cout inside verif makes my program to work and why without it nothing works.

please show the real code (including any globals etc. that are missing here), this wont compile — 463035818_is_not_an_ai, May 31 '16 at 20:40
then why do you use it in a wrong way? It is pointless to seed the rng inside a loop with `time(NULL)` unless you are working on an ancient super slow machine — 463035818_is_not_an_ai, May 31 '16 at 20:41
The reason for the above comment is since the # of seconds will not change often in your loop most of your "random" numbers will be the same since they have the same seed. — drescherjm, May 31 '16 at 20:43
@jaggedSpire I know it's in the range of [1,b] because n%p will give me p-1 maximum, that's why I add 1, so that I will have numbers from 1 to p — Peter, May 31 '16 at 20:45
@Peter fair enough. It seemed like a possible mistake, so I figured it wouldn't hurt to make sure you knew. — jaggedSpire, May 31 '16 at 20:46
You guys are criticising my program, I don't need to know how to do this correct, I'm just curious why does a cout solve the problem by not letting the program crash. — Peter, May 31 '16 at 20:48
We can't tell you that precisely, without getting an [mcve] from you. However, crashing when you remove an expression without side-effects is a pretty common indicator of Undefined Behavior. — jaggedSpire, May 31 '16 at 20:50
Agreed Undefined Behavior is the reason for the crashing / not crashing when the cout was added. — drescherjm, May 31 '16 at 20:59
@tobi303 What would be the most appropriate method to generate a random array of numbers that don't repeat? — Peter, May 31 '16 at 21:02
however in this case you're recursing while calling a function dependent on the second since the epoch returns the same result--effectively recursively calling a function for a full second, or more. With the `cout` statement the recursion is slowed enough that you don't trigger a stack overflow in that second. Without, you do. [Look at the recursion depth with and without the `sleep_for` statement](http://coliru.stacked-crooked.com/a/f9c6aad96836815d). — jaggedSpire, May 31 '16 at 21:03
@Peter That depends on how many numbers you want to pick in which range. For example when you want to choose 100 numbers at random in the range [1,100] you should use a random permutation — 463035818_is_not_an_ai, May 31 '16 at 21:04
You may be interested in this: http://en.cppreference.com/w/cpp/algorithm/random_shuffle — drescherjm, May 31 '16 at 21:13

score 4 · Answer 1 · edited May 23 '17 at 12:31

This is a result of calling a function recursively for an extended period of time, likely triggering a stack overflow on your machine.

This expression

srand(time(NULL));

seeds the random number generator for rand() to the value of the present number of seconds since the epoch. Naturally this number changes only once per second. Reseeding the rand generator will get you the same sequence as last time, so the result of rand()%100 + 1 on the following line will remain the same until the result of time(NULL) changes.

Now that you've ensured that v[i]==v[j] will be true until at least a second has passed since the initial assignment, you recursively call this function again, (and again (and again...)) until you get a new value from your "random" number generating procedure (at least a second has passed) or you run out of space on the stack. (you crash)

You can clearly see this happening much more clearly by using a function which holds up execution for longer than is taken by the cout statement, for instance

std::this_thread::sleep_for(std::chrono::milliseconds{500});

You can see such an effect here on coliru

With the sleeping function (which holds the execution up for 500 milliseconds every recursion) you get ~13 recursions.

Without it you get ~2846000 recursions. That's quite a difference.

There are better ways to get a set of non-repeating random numbers in a range, as shown in the answers to this question. I'm partial to Darklighter's answer myself. For that answer if you want, say, 10 elements out of 100, generate the vector with 100 elements, shuffle and then resize it to include only the first 10.

score 1 · Answer 2 · answered May 31 '16 at 21:11

The cout solves the problem because it takes time to print something on the console. All the rest of the code takes roughly 0 time, thus each time you do

  srand(time(NULL));
  v[i]=rand()%100+1;

You will get exactly the same number, as you always use the same seed. Then I am not 100% sure what happens, it might be a stackoverflow because you keep calling the function recursively forever, or it might be something else. Actually it doesnt really matter, because the real problem is your seed.

Only with the cout you will eventually get a differnt seed and also a different random number.

You should seed the rng only once. And btw if you want random numbers you should use the rngs from <random> and not rand (actually it should be deprecated because of its low quality).

Program works only if I keep displaying something until solution is found

2 Answers2