Compter les inversions dans un tableau

Question

Je suis en train de concevoir un algorithme pour faire ce qui suit : Étant donné un tableau A[1... n] pour chaque i < j trouver toutes les paires d'inversion telles que A[i] > A[j] . J'utilise le tri par fusion et copie le tableau A dans le tableau B, puis compare les deux tableaux, mais j'ai du mal à voir comment je peux utiliser cette méthode pour trouver le nombre d'inversions. Toute indication ou aide serait grandement appréciée.

Answer 1

C++ (n lg n) Solution avec l'impression de la paire qui constitue en compte d'inversion.

int merge(vector<int>&nums , int low , int mid , int high){
    int size1 = mid - low +1;
    int size2= high - mid;
    vector<int>left;
    vector<int>right;
    for(int i = 0  ; i < size1 ; ++i){
        left.push_back(nums[low+i]);
    }
    for(int i = 0 ; i <size2 ; ++i){
        right.push_back(nums[mid+i+1]);
    }
    left.push_back(INT_MAX);
    right.push_back(INT_MAX);
    int i = 0 ;
    int j = 0;
    int start  = low;
    int inversion = 0 ;
    while(i < size1 && j < size2){
        if(left[i]<right[j]){
            nums[start] = left[i];
            start++;
            i++;
        }else{
            for(int l = i ; l < size1; ++l){
                cout<<"("<<left[l]<<","<<right[j]<<")"<<endl;
            }
            inversion += size1 - i;
            nums[start] = right[j];
            start++;
            j++;
        }
    }
    if(i == size1){
        for(int c = j ; c< size2 ; ++c){
            nums[start] = right[c];
            start++;
        }
    }
    if(j == size2){
        for(int c =  i ; c< size1 ; ++c){
            nums[start] = left[c];
            start++;
        }
    }
    return inversion;
}
int inversion_count(vector<int>& nums , int low , int high){
    if(high>low){
        int mid = low + (high-low)/2;
        int left = inversion_count(nums,low,mid);
        int right = inversion_count(nums,mid+1,high);
        int inversion = merge(nums,low,mid,high) + left + right;
        return inversion;
    }
    return 0 ;
}

Answer 2

Solution 1 : fonctionne bien lorsqu'il y a une grande quantité de chiffres.

def countInversions(arr):
 n = len(arr)
 if n == 1:
    return 0
 n1 = n // 2
 n2 = n - n1
 arr1 = arr[:n1]
 arr2 = arr[n1:]
 # print(n1,'||',n1,'||',arr1,'||',arr2)
 ans = countInversions(arr1) + countInversions(arr2)
 print(ans)
 i1 = 0
 i2 = 0
 for i in range(n):
     # print(i1,n1,i2,n2)
     if i1 < n1 and (i2 >= n2 or arr1[i1] <= arr2[i2]):
         arr[i] = arr1[i1]
         ans += i2
         i1 += 1
     elif i2 < n2:
         arr[i] = arr2[i2]
         i2 += 1
 return ans

Solution 2. Solution simple.

def countInversions(arr):
      count = 0
      for i in range(len(arr)):
          for j in range(i, len(arr)):
               # print(arr[i:len(arr)])
                 if arr[i] > arr[j]:
                     print(arr[i], arr[j])
                     count += 1
      print(count)

Answer 3

En Java, l'algorithme de force brute fonctionne plus rapidement que l'algorithme de tri par fusion piggy backed, grâce à l'optimisation du temps d'exécution effectuée par le compilateur Java Dynamic.

Pour l'optimisation de la boucle de force brute, l'optimisation du roulement de la boucle donnera de bien meilleurs résultats.

Answer 4

Le nombre d'inversions dans un tableau est égal à la moitié de la distance totale que les éléments doivent parcourir pour trier le tableau. Par conséquent, il peut être calculé en triant le tableau, en conservant la permutation résultante p[i], puis en calculant la somme de abs(p[i]-i)/2. Cela prend O(n log n) temps, ce qui est optimal.

Une méthode alternative est donnée à http://mathworld.wolfram.com/PermutationInversion.html . Cette méthode est équivalente à la somme de max(0, p[i]-i), qui est égale à la somme de abs(p[i]-i])/2 puisque la distance totale de déplacement des éléments vers la gauche est égale à la distance totale de déplacement des éléments vers la droite.

EDIT : Cette méthode est erronée (voir les commentaires), et il n'y a malheureusement aucun moyen de la corriger tout en préservant le caractère de la méthode.