Я пишу алгоритм, который будет возвращать массив с определенной длиной и количеством инверсий (пары чисел, где левое число больше, чем правое). т.е. массив [3, 1, 4, 2] содержит три инверсии (3, 1), (3, 2) и (4, 2). Таким образом, на практике при заданной длине n=3 и количестве инверсий k=3 алгоритм должен генерировать массив [3, 1, 4, 2] (или другой массив, удовлетворяющий этим требованиям).
Поскольку количество инверсий также является количеством перестановок, которые необходимо сделать для сортировки массива в порядке возрастания, я подошел к этой проблеме, создав массив от 1 до n - 1 и используя алгоритм сортировки вставками в обратном порядке, чтобы сделать к обменивается.
Этот подход отлично работает для небольших входных данных, но алгоритм должен быть в состоянии эффективно генерировать массивы до n = 10 ^ 6 и k = n (n-1)/2 и все, что между ними, поэтому алгоритм должен работать в O (n log n) раз вместо O (n ^ 2). Ниже приведен код:
import java.util.*;
public class Inversions {
public int[] generate(int n, long k) {
// Don't mind these special cases
if (n == 1) {
int[] arr = {1};
return arr;
}
if (k == 0) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = 1;
}
return arr;
}
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i + 1;
}
int inversions = 0;
int i = 0;
while (inversions < k && i < n) {
int j = i - 1;
while (j >= 0 && arr[j] < arr[j + 1] && inversions < k) {
int helper = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = helper;
inversions++;
j--;
}
i++;
}
return arr;
}
}
И основной класс для тестирования с разными входными массивами:
public class Main {
public static void main(String[] args) {
Inversions in = new Inversions();
int[] arr1 = in.generate(4,3);
int[] arr2 = in.generate(4,0);
int[] arr3 = in.generate(4,6);
System.out.println(Arrays.toString(arr1)); // [3,1,4,2]
System.out.println(Arrays.toString(arr2)); // [1,1,1,1]
System.out.println(Arrays.toString(arr3)); // [4,3,2,1]
}
}
Алгоритм не возвращает точно такие же массивы, как и результаты выборки, но проходит все тесты, кроме тех, где размер входных данных очень велик. Я также пробовал разные варианты сортировки слиянием, поскольку она работает за время O (n log n), но безрезультатно.
Было бы здорово, если бы у вас были идеи. Если вы не знакомы с Java, не имеет значения, псевдокод или любые другие предложения более чем приветствуются!
