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.
5 Answers
Maybe the mersenne twister is wat you search for.
1 Comment
Rudy Velthuis
+1 for the link. Nah, it was for mentioning the Mersenne twister. <g>
You can create your own as follows:
int rand_n( int N )
{
return ( rand() % N ) + 1;
}
rand() is declared in stdlib.h.
2 Comments
Poulami
But i dont want to use the rand function
Praetorian
Why don't you want to use rand? Read pseudo-random number generators on Wikipedia, the external links section at the bottom has links to several implementations.
#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));
}
}
Comments
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?
Comments
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.)
rand. However you probably want to look up a shuffling algorithm.