Question about permute-by-sorting
- by davit-datuashvili
In the book "Introduction to Algorithms", second edition, there is the following problem:
Suppose we have some array:
int a[] = {1,2,3,4}
and some random priorities array:
P = {36,3,97,19}
and the goal is to permute the array a randomly using this priorities array.
This is the pseudo code:
PERMUTE-BY-SORTING (A)
1 n ? length[A]
2 for i ? 1 to n
3 do P[i] = RANDOM (1, n 3)
4 sort A, using P as sort keys
5 return A
The result should be the permuted array:
B={2, 4, 1, 3};
I have written this code:
import java.util.*;
public class Permute {
public static void main (String[] args) {
Random r = new Random();
int a[] = new int[] {1,2,3,4};
int n = a.length;
int b[] = new int[a.length];
int p[] = new int[a.length];
for (int i=0; i<p.length; i++) {
p[i] = r.nextInt(n*n*n) + 1;
}
// for (int i=0;i<p.length;i++){
// System.out.println(p[i]);
//}
}
}
How do I continue?
