Minimum calls to rand() C

Question

Edit: Sorry for the inconvinience that made because of my undetailed question.

So, i have an array of numbers (int) with 1000 cells (index 0-999) and I need to fill all the cells of the array with unique random numbers by calling the rand() function in C, but i have to do it with only 1000 calls to the fuction.. (Every number that generated is inserted to the array), there cant be duplicated numbers in the array.

Any ideas how I can do it?

Note: Here is a sample code to fill the array without limiting the number of calls to rand.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DO_RAND rand()%1000
#define ARR_SIZE 1000

int main()
{
    int i,callToRand=0,j;
    int array[ARR_SIZE];
    srand(time(NULL));
    for(i=0;i<ARR_SIZE;i++) //Runs on the whole array
    {
        array[i]=DO_RAND; //inserting random number to the array
        callToRand++; //increasing the number of calls to rand() function
        for(j=0;j<i;j++) //running on the array till the current cell
        {
            if(array[j]==array[i]) 
                //checking if the number has already in the array.
            {
                array[i]=DO_RAND;
                callToRand++;
                j=-1; //staring the checker loop again
            }
        }
    }
    printf("The number of calls to the function rand() were: %d\n",callToRand);
    system("PAUSE");
    return (0);
}

@juanchopanza beats me too..., how many calls to `rand()` are you expecting Meny? — Iharob Al Asimi, Jan 18 '15 at 20:15
Guess you forgot to read the lecture notes to answer this homework question — Ed Heal, Jan 18 '15 at 20:15
Hmmmmm.... That's a tough one!!! How about a `for` loop from 0 to 999, which calls `rand` at each iteration and stores the result at the corresponding cell within the array? Again, the problem itself looks extremely complicated to solve, so it's just a rough idea... — barak manos, Jan 18 '15 at 20:17
I was thinking about a way to solve this problem with only 1000 calls to rand() function by limiting the rand() range every time but i dont think that it will work. — Meny, Jan 18 '15 at 20:18
@Meny How is limiting the range of `rand()` related to this problem? You are greatly overthinking this. — jamesdlin, Jan 18 '15 at 20:19
So you want to set a total amount of 1000 cells to random values using **ONLY** 1000 calls to `rand`??? It sounds algorithmically impossible. Maybe it's one of those NP-complete problems, who knows... — barak manos, Jan 18 '15 at 20:19
I am not going to worry - perhaps understanding them is the next step — Ed Heal, Jan 18 '15 at 20:20
because you can play with the ranges of the rand() function, lets say the first number was 268, so the range from now on to the rand will be from 0-267 and so on, and you can save the results in a separate array, and then when the options start to end, you can do set the range to the numbers that you stored in the separate array. — Meny, Jan 18 '15 at 20:22
A wild guess with regards to OP's intention: The array needs to be filled with **unique** random values, ranging from 0 to 999 (a.k.a. the most famous job-interview question in all times). — barak manos, Jan 18 '15 at 20:24
@Meny You are either grossly misunderstanding the problem or you're misstating it (must the numbers in the array be *unique*?). — jamesdlin, Jan 18 '15 at 20:25
If they must be unique they are not random. It is possible to throw a dice four times and each time get snakes eyes — Ed Heal, Jan 18 '15 at 20:28
@Meny Ah, ok. *That* is a different problem than what you actually asked (and one that wouldn't have deserved all of the downvotes and the snarkiness). Edit your question and state what you actually want. For example, must the array contain all numbers from [0, 999] in random order? Or must they contain randomly chosen numbers with no duplicates? — jamesdlin, Jan 18 '15 at 20:29
Fill the array with numbers 0-999 in increasing order. Then swap each number in the array with a random other number.This gives you 1000 calls to the `rand` function. You will have shuffled the list completely, like a deck of cards. — Erwin Bolwidt, Jan 19 '15 at 08:23
There are at least two algorithms that will fill the array with unique random numbers in non-random order using only 1000 calls to `rand()`. But to achieve random order extra calls to `rand()` will be necessary for the post-shuffle. — AnT stands with Russia, Jan 19 '15 at 08:28
@Erwin Bolwidt: The OP never said the numbers must belong to `[0..999]` range. According to the given statement of the problem, the numbers come from the full `[0..RAND_MAX]` range. — AnT stands with Russia, Jan 19 '15 at 08:31
@AndreyT But it can be 0-999. There's no restriction that it can't be. Erwin's solution seems feasible to me — nj-ath, Jan 19 '15 at 08:37
@AndreyT The sample code from the OP restricts numbers to the 0-999 range. — Erwin Bolwidt, Jan 19 '15 at 08:37
@Erwin Bolwidt: If that's the case then obviously the classic random shuffle using Knuth algorithm is all the OP needs. — AnT stands with Russia, Jan 19 '15 at 08:38
@ErwinBolwidt While your approach might satisfy the OP's requirements, it is biased. See http://blog.codinghorror.com/the-danger-of-naivete/ — jamesdlin, Jan 28 '15 at 11:19

score 1 · Accepted Answer · answered Jan 20 '15 at 17:34

Having finally stated that you want an array of unique numbers within the range of the array size, try this. Note that the numbers are not randomised - they are defined - the sequence is.

Your posted attempt was very inefficient, using two nested loops. This uses one loop to initialise the array and another to randomise the sequence. No need to count the calls to rand() which are obviously ARR_SIZE.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARR_SIZE 100 //1000

int main()
{
    int i, j, temp;
    int array[ARR_SIZE];
    srand((unsigned)time(NULL));
    for(i=0; i<ARR_SIZE; i++)       // set up unique array
        array[i] = i;

    for(i=0; i<ARR_SIZE; i++) {     // randomize the sequence
        j = rand() % ARR_SIZE;      // pick another (or same) index
        temp = array[i];            // and swap the values
        array[i] = array[j];
        array[j] = temp;
    }

    for(i=0; i<ARR_SIZE; i++)       // show results
        printf ("%5d", array[i]);
    printf ("\n");
    return (0);
}

Note that this approach of iterating over the array and swapping it with a random other element in the array will not produce a random shuffle; the resulting array will be biased. There also will be bias from the way that you restrict `rand()` into a certain range. Also see: http://stackoverflow.com/a/27759739/179715 — jamesdlin, Jan 28 '15 at 11:24
@jamesdlin thank you, I was aware of your second point but not the first, although I suspected it was not the best way because some elements will be swapped more than once. A better answer would have been using a method like the answer linked below, which I gather was originally credited to Fisher and Yates, but this post was an exasperated afterthought to OP's lack of clarity. http://stackoverflow.com/questions/27867248/how-to-make-a-random-generation-number-between-1-to-9-without-repitition/27867571#27867571 — Weather Vane, Jan 28 '15 at 23:23

Minimum calls to rand() C

1 Answers1