domingo, 3 de junho de 2012

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 ai > aj, ou seja, se dois elementos  ai e aj 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 (ai,aj) e determinar se eles formam uma inversão; isto seria O(n2).
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 a1,..,am e am+1,…,an. Primeiramente, vamos contar o número de inversões em cada metade separadamente. Então vamos contar o  número de inversões (ai,aj), 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 ai for colocado na lista ordenada, nenhuma inversão é encontrada, uma vez que ai é menor que todos os elementos da lista B. Por outro lado, se bj for colocado na lista ordenada, então bj é 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.

























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.

2 comentários:

Anônimo disse...

Mt bom! :D
Esse algoritmo ajuda tbm no http://br.spoj.pl/problems/BALE11/

Acassio disse...

Cara muito bom o algoritmo e parabéns pela postagem, consegui resolver todos menos o SWAPS do SPOJ, toda vez que chamo a função ele ordena os vetores e não mantem a ordem de antes. E fiz contando de um em um e recebi um TLE esperado... Como faço essa????? Já tentou esse problema?