Алгоритм для оценки монотонности массива (т.е. оценки «сортировки» массива)

Question

---

РЕДАКТИРОВАТЬ : Вау, много хороших ответов. Да, я использую это как функцию пригодности для оценки качества сортировки, выполняемой генетическим алгоритмом. Таким образом, стоимость оценки важна (то есть она должна быть быстрой, предпочтительно O(n).)

---

Как часть приложения ИИ, с которым я играю, я бы хотел иметь возможность оценивать массив целых чисел-кандидатов на основе его монотонности, то есть его "сортировки". На данный момент я использую эвристику, которая вычисляет самый длинный отсортированный прогон, а затем делит его на длину массива:

public double monotonicity(int[] array) {
    if (array.length == 0) return 1d;

    int longestRun = longestSortedRun(array);
    return (double) longestRun / (double) array.length;
}

public int longestSortedRun(int[] array) {

    if (array.length == 0) return 0;

    int longestRun = 1;
    int currentRun = 1;

    for (int i = 1; i < array.length; i++) {
        if (array[i] >= array[i - 1]) {
            currentRun++;
        } else {
            currentRun = 1;
        }

        if (currentRun > longestRun) longestRun = currentRun;
    }

    return longestRun;
}

Это хорошее начало, но оно не учитывает вероятность того, что могут быть "скопления" отсортированных подпоследовательностей. E.g.:

{ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9}

Этот массив разделен на три отсортированные подпоследовательности. Мой алгоритм оценит его как отсортированный только на 40%, но интуитивно он должен получить более высокий балл, чем этот. Существует ли стандартный алгоритм для такого рода вещей?

Answer 1

Это кажется хорошим кандидатом на Левенштейна Дамерау – Левенштейна расстояние - количество обменов, необходимое для сортировки массива. Это должно быть пропорционально тому, как далеко каждый элемент от того, где он должен быть в отсортированном массиве.

Вот простой алгоритм ruby, который суммирует квадраты расстояний. Это кажется хорошей мерой сортировки - результат уменьшается каждый раз, когда два неупорядоченных элемента меняются местами.

ap = a.sort
sum = 0
a.each_index{|i| j = ap.index(a[i])-i 
  sum += (j*j)
}
dist = sum/(a.size*a.size)

Answer 2

Я ожидаю, что выбор используемой функции очень сильно зависит от того, для чего вы собираетесь ее использовать. Исходя из вашего вопроса, я бы предположил, что вы используете генетическую систему для создания программы сортировки, и это должно быть функцией ранжирования. Если это так, то скорость исполнения имеет решающее значение. Исходя из этого, держу пари, ваш алгоритм самой длинной отсортированной подпоследовательности будет работать очень хорошо. Звучит так, как будто это должно хорошо определять физическую форму.

Answer 3

Что вы, вероятно, ищете, это Кендалл Тау . Это однозначная функция расстояния сортировки пузырьков между двумя массивами. Чтобы проверить, является ли массив «почти отсортированным», вычислите его Kendall Tau по отсортированному массиву.

Answer 4

Вычислите длины всех отсортированных подпоследовательностей, затем возведите их в квадрат и сложите их. Если вы хотите откалибровать, сколько энфазиса вы используете, используйте мощность, отличную от 2.

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

Answer 5

Вот один, который я только что составил.

Для каждой пары смежных значений рассчитайте числовую разницу между ними. Если второе больше или равно первому, добавьте это к итогу sorted, в противном случае добавьте к итогу unsorted. Когда закончите, возьмите соотношение двух.

Answer 6

Как то так? http://en.wikipedia.org/wiki/Rank_correlation

Answer 7

У меня та же проблема (оценка монотонности), и я предлагаю вам попробовать Longest возрастающая подпоследовательность . Самый эффективный алгоритм работает в O(n log n), не так уж и плохо.

Принимая пример из вопроса, самая длинная возрастающая последовательность {4, 5, 6, 0, 1, 2, 3, 7, 8, 9} равна {0, 1, 2, 3, 7, 8, 9} (длина 7). Может быть, это лучше (70%), чем ваш самый длинный алгоритм сортировки.

Answer 8

Я бы предложил взглянуть на Блинную проблему и расстояние перестановок перестановок. Эти алгоритмы часто используются, чтобы найти расстояние между двумя перестановками (Идентичность и переставленная строка). Эта мера расстояния должна учитывать больше скоплений значений порядка, а также инверсии (монотонно уменьшающиеся вместо увеличивающихся подпоследовательностей). Есть также аппроксимации полиномиального времени [PDF] .

На самом деле все зависит от того, что означает число, и если эта функция расстояния имеет смысл в вашем контексте.

Answer 9

Как насчет подсчета количества шагов с увеличением значения по сравнению с количеством полных шагов. Это O(n).

Answer 10

Некоторые эксперименты с модификатором Ratcliff & Obershelp

>>> from difflib import SequenceMatcher as sm
>>> a = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ]
>>> c = [ 0, 1, 9, 2, 8, 3, 6, 4, 7, 5 ]
>>> b = [ 4, 5, 6, 0, 1, 2, 3, 7, 8, 9 ]
>>> b.sort()
>>> s = sm(None, a, b)
>>> s.ratio()
0.69999999999999996
>>> s2 = sm(None, c, b)
>>> s2.ratio()
0.29999999999999999

Так что вроде делает то, что нужно. Не слишком уверен, как это доказать.