Algoritmo per aver valutato la monotonia di una matrice (cioè giudicare la "sortedness" di un array)

Question

---

EDIT: Wow, molte risposte grande. Sì, sto usando questo come funzione di fitness per giudicare la qualità di un tipo eseguito da un algoritmo genetico. Così costo della valutazione è importante (ad esempio, deve essere veloce, preferibilmente O(n).)

---

Come parte di un programma AI sto accarezzando, mi piacerebbe essere in grado di votare un candidato array di interi in base alla sua monotonicità, ovvero la sua "ordinata". Al momento, sto usando un euristica che calcola la più lunga ordinato, e poi divide che entro la lunghezza dell'array:

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

Questo è un buon inizio, ma non riesce a prendere in considerazione la possibilità di che potrebbero esserci "raggruppamenti" di sottosequenze ordinate. Es .:

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

Questo array è suddiviso in tre sottosequenze ordinate. Il mio algoritmo valuterà come solo il 40% ordinato, ma intuitivamente, dovrebbe ottenere un punteggio più alto di quello. Esiste un algoritmo standard per questo genere di cose?

Answer 1

Mi aspetto che la scelta della funzione da utilizzare dipenda molto fortemente da cosa si intende utilizzare. In base alla tua domanda, suppongo che tu stia utilizzando un sistema genetico per creare un programma di ordinamento, e questa deve essere la funzione di classificazione. Se questo è il caso, allora la velocità di esecuzione è cruciale. Sulla base di questo, scommetto che il tuo algoritmo di sequenziamento più lungo potrebbe funzionare abbastanza bene. Sembra che dovrebbe definire abbastanza bene la forma fisica.

Answer 2

questo mi sembra un buon candidato per Levenshtein Damerau–Levenshtein distanza - il numero di swap necessari per ordinare l'array. Questo dovrebbe essere proporzionale alla distanza di ciascun oggetto da dove dovrebbe trovarsi in un array ordinato.

Ecco un semplice algoritmo di ruby ​​che somma i quadrati delle distanze. Sembra una buona misura di ordine - il risultato diventa più piccolo ogni volta che vengono scambiati due elementi fuori ordine.

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

Qualcosa come questi?

Answer 4

Suggerirei di guardare lo Pancake Problem e la distanza di inversione delle permutazioni. Questi algoritmi sono spesso usati per trovare la distanza tra due permutazioni (l'identità e la stringa permutata). Questa misura di distanza dovrebbe tenere conto di più gruppi di valori dell'ordine e di inversioni (diminuzione monotona invece di sottosequenze crescenti). Ci sono anche approximations that are polynomial time[PDF].

Tutto dipende da cosa significa il numero e se questa funzione di distanza ha comunque senso nel contesto.

Answer 5

Dipende molto da cosa si intende utilizzare la misura, ma un modo semplice per farlo è alimentare l'array in un algoritmo di ordinamento standard e misurare il numero di operazioni (swap e/o confronti) necessari essere fatto per ordinare l'array.

Answer 6

Eccone uno che ho appena inventato.

Per ciascuna coppia di valori adiacenti, calcolare la differenza numerica tra di essi.Se il secondo è maggiore o uguale al primo, aggiungilo al totale sorted, altrimenti aggiungi al totale unsorted. Al termine, prendi il rapporto dei due.

Answer 7

Calcola le lunghezze di tutte le sottosequenze ordinate, quindi piazza e aggiungi. Se si desidera calibrare la quantità di enfasi più grande, utilizzare una potenza diversa da 2.

Non sono sicuro quale sia il modo migliore per normalizzare questo per lunghezza, magari dividerlo per lunghezza al quadrato?

Answer 8

Alcuni esperimenti con un modificatore 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 

Quindi tipo di fa quello che deve. Non sono troppo sicuro di come provarlo.

Answer 9

Quello che stai probabilmente cercando è Kendall Tau. È una funzione uno a uno della distanza del tipo di bolla tra due array. Per verificare se un array è "quasi ordinato", calcola il suo Kendall Tau contro un array ordinato.

Answer 10

Ho lo stesso problema (punteggio di monotonicità) e suggerisco di provare Longest Increasing Subsequence. L'algoritmo più efficiente eseguito in O(n log n), non così male.

Prendendo esempio dalla domanda, la sequenza crescente più lunga di {4, 5, 6, 0, 1, 2, 3, 7, 8, 9} è {0, 1, 2, 3, 7, 8, 9} (lunghezza di 7). Forse è migliore (70%) rispetto all'algoritmo di elaborazione più lunga.

Answer 11

Come contare il numero di passaggi con valore crescente rispetto al numero di passaggi totali. Questo è O(n).