Data Structures andAlgorithm Analysis in Java E3, question 2.8: Suppose you need

Question

Data Structures andAlgorithm Analysis in Java E3, question 2.8:

Suppose you need to generate a random permutation of the first N integers.

For example, {4, 3, 1, 5, 2} and {3, 1, 4, 2, 5} are legal permutations, but

{5, 4, 1, 2, 1} is not, because one number (1) is duplicated and another (3) is

missing. This routine is often used in simulation of algorithms. We assume the exis-
tence of a random number generator, r, with method randInt(i, j), that generates

integers between i and j with equal probability. Here are three algorithms:

Explanation / Answer

Can help you with this any help please comment

int k = rand() % j;
Now, k is a random number in the range 0..j-1.

Here is the shuffle:

enum { N = 5, }; // for example.
int numbers[N];
for (int i = 0; i < N; ++i) numbers[i] = i + 1;
for (int i = N; i > 2; )
{
int k = rand() % i;
int tmp = numbers[--i];
numbers[i] = numbers[k];
numbers[k] = tmp;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.