Contando número de Inversões

Este problema surge na análise de rankings (classificações) que tem ser tornado importante para um grande número de aplicações. Por exemplo, considere  uma ferramenta de meta-search na internet, que executa uma mesma query em diferentes motores de buscas (search engines)  como Google,Yahoo entre outros  e tenta sintetiza o resultados procurando por similaridades e diferenças entre os vários rankings que são retornados pelos motores de busca.

Outra aplicação interessante seria comparar um conjunto de rankings sobre alguma preferência (livros, filmes, restaurantes) para criar um tipo de filtro colaborativo.

Agora, qual é a melhor medida que pode ser usada para saber quão similar são duas classificações?

Problema

Uma maneira natural seria quantificar a noção de similaridade é contando o número de inversões. Nós dizemos que dois índices i < j formam uma inversão se a_i > a_j, ou seja, se dois elementos  a_i e a_j estão fora de ordem.

Existe um apelo geométrico para visualiza o número de inversões em uma permutação.

Neste exemplo, temos 3  inversões nestas sequência: (2,1), (4,1) e (4,3). Note que uma cada intersecção de um par de segmentos corresponde a uma inversão.

Modelando e Analisando o Algoritmo

O algoritmo ingênuo para contar as inversões seria checar todos os pares de números (a_i,a_j) e determinar se eles formam uma inversão; isto seria O(n²).

Nós vamos mostrar como contar o número de inversão muito mais rapidamente, em O(n log n). Observe que todo par pode formar uma inversão, e então existe no máximo  inversões. Logo, o número de inversões é quadrático. Dessa maneira, o algoritmo que vamos desenvolver tem que ser capaz de computar o total de inversões sem precisar checar cada inversão individualmente.

Idéia Básica

Considere m = $\lfloor \frac{n}{2} \rfloor$ e divida a lista em duas sublistas a₁,..,a_m e a_m+1,…,a_n. Primeiramente, vamos contar o número de inversões em cada metade separadamente. Então vamos contar o  número de inversões (a_i,a_j), onde os dois números pertencem a metades diferentes; o truque é fazer esta parte em O(n).

Vamos fazer uma adaptação do algoritmo Merge-Sort.

 

Durante a intercalação, precisamos contar o número de inversões. 

Se o elemento a_i for colocado na lista ordenada, nenhuma inversão é encontrada, uma vez que a_i é menor que todos os elementos da lista B. Por outro lado, se b_j for colocado na lista ordenada, então b_j é menor que todos os elementos restantes em A, e ele aparece depois de todos eles, então nós precisamos incrementar o número de inversões pelo número de elementos restantes em A. Esta é a idéia crucial: em tempo constante, nós podemos calcular um número grande de inversões em potencial.

 Fonte das figuras: http://www.ime.usp.br/~cris/mac5711/aulas/final-aula1.pdf

long long int merge_count(int A[], int B[], int p,int q,int r){
 int i,j,k;
 
 long long int c;
 
 for(i=p;i<=q;i++)
  B[i] = A[i];
  
 for(j=q+1;j<=r;j++)
  B[r+q+1-j]=A[j];
  
 i = p;
 j = r;
 c = 0; 
 
 for(k=p;k<=r;k++){
  if(B[i] <= B[j]){
   A[k] = B[i];
   i = i+1;
  }else{
   A[k] = B[j];
   j = j-1;
   c = c + (q-i+1);
  }
 }
 
 return c;

}



long long int sort_count(int A[], int B[], int i,int j){
 int q;
 if(i >=j ) return 0;
 else{
  q = (i+j)/2;
  return sort_count(A, B, i, q) +
      sort_count(A, B, q+1, j)+
      merge_count(A, B, i, q, j);  
 } 
 
}

Problema

Lembrando que o número de inversões é O( $ \binom {n} {2} $ ) . Em alguns casos pode estourar a capacidade de inteiro de 32-bit.

https://www.spoj.pl/problems/INVCNT/

http://br.spoj.pl/problems/BALDES/

http://www.spoj.pl/problems/SWAPS/

http://code.google.com/codejam/contest/dashboard?c=619102#s=p0&a=0