Returning a random number from a range of numbers using C

An array of integers of size n.开发者_如何学运维 I need to generate a random permutation of the array, given a function rand_n() that returns an integer between 1 and n, both inclusive, with equal probability. I know about the random function in java but I want to implement it using C.

Maybe the mersenne twister is wat you search for.

You can create your own as follows:

int rand_n( int N )
{
  return ( rand() % N ) + 1;
}

rand() is declared in stdlib.h.

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

int randint(int min, int max) 
{ 
    if (min>max) 
    { 
        return max+(int)((min-max+1)*rand()/(RAND_MAX+1.0)); 
    } 
    else 
    { 
        return min+(int)((max-min+1)*rand()/(RAND_MAX+1.0)); 
    } 
}

If I understood correctly, the question is not about writing a PRNG, it's about using a predefined rand_n function to write an algorithm to shuffle the array. Writing a PRNG is not trivial, I doubt they'd ask you that in an interview. But a shuffling algorithm is a different story. Here's one, in pseudocode, off the top of my head:

Iteration 1:

• Fill an array with the numbers from 1 to N, let's call it positions
• i = rand_n(N);
• shuffled[0] = toShuffle[ positions[i] ];
• Delete i from positions and resize it (now it has N-1 elements)

Iteration 2:

• i = rand_n(N-1)
• shuffled[1] = toShuffle[ positions[i] ];
• Delete i from positions and resize it (now it has N-2 elements)

...Catch my drift?

Take a look at the Fisher-Yates shuffle. This produces a random permutation of an array by randomly swapping elements (thus using a simple rand_n type function to select the elements.)