Вопрос о перестановке по сортировке

Question

В книге «Введение в алгоритмы», второе издание, есть следующая проблема:

Предположим, у нас есть некоторый массив:

int a[] = {1,2,3,4}

и некоторый массив случайных приоритетов:

P = {36,3,97,19}

и цель состоит в том, чтобы случайным образом переставить массив a, используя этот массив приоритетов.

Это псевдокод:

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

Результатом должно бытьПереставленный массив:

B={2, 4, 1, 3};

Я написал этот код:

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]);
        //}
    }
}

Как продолжить?

Answer 1

Я не уверен, с какой частью у вас проблемы, но по сути это то, что произошло:

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

Как бы вы ни думали об этом, по сути, мы хотим «сжать» элементы этих двух списков вместе. Итак, на абстрактном уровне мы имеем следующее:

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

Теперь мы сортируем zipped по второму значению в Pair. Какой бы алгоритм сортировки ни работал; это не имеет значения.

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

Затем мы распаковываем пары, чтобы получить перестановку a:

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

---

Как реализовать

Zip-into- Pair -then-unzip работает просто отлично. В противном случае вы можете изменить алгоритм сортировки таким образом, чтобы при перемещении элементов с p[i] на p[j] он также перемещался с a[i] на a[j], чтобы оба массива были синхронизированы.

---

Фрагмент Java

В следующем фрагменте массив priorities жестко закодирован с указанными выше значениями. Вы уже выяснили, как посеять случайные числа.

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]"
    }
}