Алгоритм рейтинга монотонности массива (то есть, судя по «sortedness» массив)

Question

---

EDIT: Ничего себе, много больших ответов. Да, я использую это как функцию пригодности для оценки качества сортировки, выполняемой генетическим алгоритмом. Таким образом, в стоимости оценки является важным (то есть, он должен быть быстрым, предпочтительно O(n).)

---

В рамках приложения AI Я играю с, я хотел бы быть в состоянии оценить кандидата массив целых чисел, основанный на его монотонности, а также его «сортировка». На данный момент я использую эвристику, которая вычисляет самый длинный отсортированный бег, а затем делит на длину массива:

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; 
} 

Это хорошее начало, но он не принимает во внимание возможность что могут быть «комки» отсортированных подпоследовательностей. Например:

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

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

Answer 1

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

Answer 2

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

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

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 3

Нечто подобное? http://en.wikipedia.org/wiki/Rank_correlation

Answer 4

Я бы предложил посмотреть на Pancake Problem и на разворотные расстояния перестановок. Эти алгоритмы часто используются для нахождения расстояния между двумя перестановками (Identity и перестановочная строка). Эта дистанционная мера должна учитывать больше скоплений значений порядка, а также развороты (монотонно уменьшаясь, а не увеличивая подпоследовательности). Есть также approximations that are polynomial time[PDF].

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

Answer 5

Это очень зависит от того, на что вы намерены использовать меру, но один простой способ сделать это - передать массив в стандартный алгоритм сортировки и измерить, сколько операций (свопов и/или сравнений) необходимо для сортировки массива.

Answer 6

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

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

Answer 7

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

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

Answer 8

Некоторые эксперименты с модификатором 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 

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

Answer 9

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

Answer 10

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

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

Answer 11

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