calcolo del numero di "inversioni" in una permutazione

Question

Sia A un array di dimensioni N. noi chiamiamo un paio di indici (i,j) un "inversa", se i < j e A[i] > A[j]

Ho bisogno di trovare un algoritmo che riceve un array di dimensione N (con numeri univoci) e restituire il numero di inversi in tempo di O(n*log(n)).

Answer 1

È possibile utilizzare l'algoritmo merge sort.

Nel ciclo dell'algoritmo di fusione, le metà sinistra e destra sono entrambe ordinate in modo ascendente e vogliamo unirle in un unico array ordinato. Nota che tutti gli elementi nella parte destra hanno indici più alti di quelli nella parte sinistra.

Assumere array [leftIndex]> array [rightIndex]. Ciò significa che tutti gli elementi nella parte sinistra che seguono l'elemento con indice leftIndex sono anche più grandi di quello corrente nella parte destra (poiché il lato sinistro è ordinato in ordine ascendente). Quindi l'elemento corrente nella parte destra genera numberOfElementsInTheLeftSide - leftIndex + 1 inversioni, quindi aggiungilo al conteggio dell'inversione globale.

Una volta che l'algoritmo ha terminato l'esecuzione, si ottiene la risposta e l'unire l'ordinamento è O (n log n) nel peggiore dei casi.

Answer 2

C'è un articolo pubblicato in SIAM nel 2010 da Cham e Patrascu dal titolo Counting Inversions, Offline Orthogonal Range Counting, and Related Problems che fornisce un algoritmo che utilizza O (n sqrt (log (n))). Questo è attualmente l'algoritmo più noto e migliora l'algoritmo O (n log (n)/log (log (n))) di vecchia data. Dall'estratto:

Diamo un O (n sqrt (lg n)) algoritmo con tempo per contare il numero di inversioni in una permutazione su n elementi. Questo migliora una lunga precedente rilegato di O (n lg n/lg lg n) che seguita dalla struttura di dati di Dietz [WADS'89], e risponde ad una domanda di Andersson e Petersson [SODA'95 ]. Come il risultato di Dietz è noto per essere ottimale per il problema relativo al rank dinamico, il nostro risultato dimostra un significativo miglioramento nell'impostazione offline offline.

La nostra nuova tecnica è molto semplice: abbiamo eseguiamo una "suddivisione verticale" di un trie (simile ad alberi van Emde Boas), e usare le idee dalla memoria esterna. Tuttavia, la tecnica trovano numerose applicazioni: ad esempio, otteniamo

• in d dimensioni, un algoritmo per risposta n offline ortogonali gamma query conteggio in tempo O (n lg ^{d-2 + 1/d} n);
• un tempo di costruzione migliorato per dati online strutture per campo ortogonale conteggio;
• un tempo di aggiornamento migliorato per il problema di somme parziali;
• veloce algoritmi Word RAM per trovare il profondità massima in una disposizione di rettangoli assi allineati, e per il problema della selezione pendenza.

Come bonus, diamo anche un semplice algoritmo -approximation (1 + ε) per inversioni conteggio che viene eseguito in tempo lineare, migliorando il precedente O (n lg lg n) bound di Andersson e Petersson.

Answer 3

Penso che il modo più esagerato per fare questo (e questo solo perché amo la struttura dei dati) è usare un binary indexed tree. Intendiamoci, se tutto ciò di cui avete bisogno è una soluzione, unire sort funzionerebbe altrettanto bene (penso solo che questo concetto sia assolutamente dannoso!). L'idea di base è questa: creare una struttura dati che aggiorni i valori in O (log n) e risponda alla query "Quanti numeri in meno di x si sono già verificati nell'array fino ad ora?" Detto questo, puoi facilmente rispondere a quanti sono maggiori di x che contribuisce alle inversioni con x come secondo numero nella coppia. Ad esempio, considera l'elenco {3, 4, 1, 2}.

Durante l'elaborazione 3, non ci sono altri numeri finora, così inversioni con 3 sul lato destro = 0 Durante l'elaborazione 4, il numero di numeri inferiori a 4 finora = 1, quindi il numero di numeri maggiori (e quindi inversioni) = 0 Ora, durante l'elaborazione di 1, numero di numeri inferiore a 1 = 0, questo numero di numeri maggiori = 2 che contribuisce a due inversioni (3,1) e (4,1). La stessa logica si applica a 2 che trova 1 numero in meno di esso e quindi 2 maggiore di esso.

Ora, l'unica domanda è capire come questi aggiornamenti e query si verificano nel registro n. L'url di cui sopra è uno dei migliori tutorial che ho letto sull'argomento.

Answer 4

Questi sono i MERGE originale e unire fascicolazione algoritmi da Cormen, Leiserson, Rivest, Stein Introduzione agli algoritmi:

MERGE(A,p,q,r) 
1 n1 = q - p + 1 
2 n2 = r - q 
3 let L[1..n1 + 1] and R[1..n2 + 1] be new arrays 
4 for i = 1 to n1 
5  L[i] = A[p + i - 1] 
6 for j = 1 to n2 
7  R[j] = A[q + j] 
8 L[n1 + 1] = infinity 
9 R[n2 + 1] = infinity 
10 i = 1 
11 j = 1 
12 for k = p to r 
13  if L[i] <= R[j] 
14   A[k] = L[i] 
15   i = i + 1 
16  else A[k] = R[j] 
17   j = j + 1 

e

MERGE-SORT(A,p,r) 
1 if p < r 
2  q = floor((p + r)/2) 
3  MERGE-SORT(A,p,q) 
4  MERGE-SORT(A,q + 1,r) 
5  MERGE(A,p,q,r) 

alla linea 8 e 9 in MERGE all'infinito è la cosiddetta carta sentinella, che ha un valore tale che tutti gli elementi dell'array sono più piccoli di esso. Per ottenere il numero di inversione si può introdurre un contatore globale, diciamo ninv inizializzato a zero prima di chiamare MERGE-SORT e poi di modificare l'algoritmo MERGE aggiungendo una riga nella dichiarazione else dopo la riga 16, qualcosa come

ninv += n1 - i 

che dopo MERGE-SORT è finito NINV conterrà il numero di inversioni