Я пишу алгоритм, который будет возвращать массив с определенной длиной и числом инверсий (пары чисел, где номер левой стороны больше, чем номер правой стороны).Т.е. массив [3, 1, 4, 2] содержит три инверсии (3, 1), (3, 2) и (4, 2).Таким образом, на практике, когда заданы длина n = 3 и число инверсий k = 3, алгоритм должен генерировать массив [3, 1, 4, 2] (или другой массив, который удовлетворяет этим требованиям).
Поскольку число инверсий - это также число перестановок, которые необходимо выполнить для сортировки массива в порядке возрастания, я решил эту проблему, создав массив от 1 до n - 1 и используя вставкуалгоритм сортировки в обратном порядке, чтобы сделать k перестановок.
Этот подход прекрасно работает для небольших входных данных, но алгоритм должен иметь возможность эффективно генерировать массивы до 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 time), но безрезультатно.
Было бы замечательно, если бы у вас, ребята, были какие-то идеи.Если вы не знакомы с Java, не имеет значения, псевдокод или любые другие предложения приветствуются!