Question

Como implementar um programa para contar as inversões de uma sequência?

Answer 1

Os dois códigos abaixo fazem isso. O primeiro baseado em força bruta comparando todos os termos. O segundo usando explicitamente o merge_sort que é usado para ordenar sequências.

import numpy as np

# Algoritmo forca bruta
def counting_inversions(sequence):
    n=sequence.size
    numberInversions=0
    for i in range(0,n):
        for j in range(i+1,n):
            if(sequence[i]>sequence[j]):
                numberInversions=numberInversions+1
    return numberInversions

# Algoritmo usando o paradigma de divisao e conquista (de fato, usando merge_sort)
def merge(a,b):
    na=a.size
    nb=b.size
    c=np.empty([na+nb],int)    
    i=0
    j=0
    z=0
    count=-1;
    while((i<=na-1)and(j<=nb-1)):
        count=count+1    
        if(a[i]<b[j]):
            c[count]=a[i]
            i=i+1
        else:
            c[count]=b[j]  
            z=z+(na-i)
            j=j+1

    if(count<na+nb-1):
        if(i<=na-1):
            for k in range(count+1,na+nb):
                c[k]=a[i]
                i=i+1
        else:
            for k in range(count+1,na+nb):
                c[k]=b[j]
                j=j+1
    return (c,z)       

def merge_sort(a):
    n=a.size
    x=0
    y=0
    z=0    
    if(n>1):
        b=a[0:n//2]
        c=a[n//2:n]
        [b,x]=merge_sort(b)
        [c,y]=merge_sort(c)
        [a,z]=merge(b,c)
    return (a,x+y+z)      


a=np.array([5,6,4,3,1,2])

print "numberInversions="
print counting_inversions(a)

print "numberInversionsRecursive="
print merge_sort(a)