Question about permute-by-sorting

Question

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?

Answer 1

I'm not sure which part you're having trouble with, but essentially this is what happened:

int[] a = {  1,  2,  3,  4 };
int[] p = { 36,  3, 97, 19 };

However you think about it, essentially we want to "zip" the elements of these two lists together. So at the abstract level, we have the following:

Pair<int,int> zipped = { ( 1,36), ( 2, 3), ( 3,97), ( 4,19) };

Now we sort zipped by the second value in the Pair. Whatever sorting algorithm works; it doesn't really matter.

zipped = { ( 2, 3), ( 4,19), ( 1,36), ( 3,97) };

We then unzip the pairs to get the permuted a:

a = {  2,  4,  1,  3 };
p = {  3, 19, 36, 97 };

---

How to implement

The zip-into-Pair-then-unzip works just fine. Otherwise, you can modify the sorting algorithm so that whenever it moves elements of p[i] to p[j], it also moves a[i] to a[j] to keep both arrays "in-sync".

---

Java snippet

In the following snippet, the priorities array is hardcoded to the above values. You already figured out how to seed it with random numbers.

import java.util.*;

public class PermuteBySorting {
    public static void main(String[] args) {
        class PrioritizedValue<T> implements Comparable<PrioritizedValue<T>> {
            final T value;
            final int priority;
            PrioritizedValue(T value, int priority) {
                this.value = value;
                this.priority = priority;
            }
            @Override public int compareTo(PrioritizedValue other) {
                return Integer.valueOf(this.priority).compareTo(other.priority);
            }           
        }
        int[] nums = { 1, 2, 3, 4 };
        int[] priorities = { 36, 3, 97, 19 };
        final int N = nums.length;
        List<PrioritizedValue<Integer>> list =
            new ArrayList<PrioritizedValue<Integer>>(N);
        for (int i = 0; i < N; i++) {
            list.add(new PrioritizedValue<Integer>(nums[i], priorities[i]));
        }
        Collections.sort(list);
        int[] permuted = new int[N];
        for (int i = 0; i < N; i++) {
            permuted[i] = list.get(i).value;
        }
        System.out.println(Arrays.toString(permuted));
        // prints "[2, 4, 1, 3]"
    }
}