// Class Random provides a pseudo random number generator. Initialize
// with a positive integer seed value (if no seed is provided 1 is used).
// Public operation randInt() produces a pseudo random value between
// 1 and 2^31 - 1.
class Random
{
private:
int state;
static const int A = 48271;
static const int M = 2147483647;
static const int Q = M/A;
static const int R = M%A;
public:
Random()
{state = 1;}
Random(int initvalue)
{state = initvalue; if (state<=0) state=1;}
int randInt()
{
int tmp = A*(state%Q) - R*(state/Q);
if (tmp>=0) state = tmp; else state = tmp + M;
return state;
}
};
// Code for generating a random permutation of 1, ..., N
int a[n];
Random r(seed);
for (int i = 0; i < n; i++) a[i] = i + 1;
for (int j = 1; j < n; j++) exch( a[j], a[r.randInt()%j] );