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

Voici donc une solution O(n log n) en java.

long merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, count = 0;
    while (i < left.length || j < right.length) {
        if (i == left.length) {
            arr[i+j] = right[j];
            j++;
        } else if (j == right.length) {
            arr[i+j] = left[i];
            i++;
        } else if (left[i] <= right[j]) {
            arr[i+j] = left[i];
            i++;                
        } else {
            arr[i+j] = right[j];
            count += left.length-i;
            j++;
        }
    }
    return count;
}

long invCount(int[] arr) {
    if (arr.length < 2)
        return 0;

    int m = (arr.length + 1) / 2;
    int left[] = Arrays.copyOfRange(arr, 0, m);
    int right[] = Arrays.copyOfRange(arr, m, arr.length);

    return invCount(left) + invCount(right) + merge(arr, left, right);
}

C'est un tri par fusion presque normal, toute la magie est cachée dans la fonction de fusion. Notez que l'algorithme de tri supprime les inversions. Pendant la fusion, l'algorithme compte le nombre d'inversions supprimées (triées, pourrait-on dire).

Le seul moment où les inversions sont supprimées est lorsque l'algorithme prend un élément du côté droit d'un tableau et le fusionne avec le tableau principal. Le nombre d'inversions supprimées par cette opération est le nombre d'éléments restants du tableau de gauche à fusionner :)

J'espère que c'est suffisamment explicatif.

Answer 2

Je l'ai trouvé en temps O(n * log n) par la méthode suivante.

1. Fusionner le tableau de tri A et créer une copie (tableau B)

2. Prenez A[1] et trouvez sa position dans le tableau trié B par une recherche binaire. Le nombre d'inversions pour cet élément sera inférieur d'une unité au numéro d'index de sa position dans B puisque chaque nombre inférieur qui apparaît après le premier élément de A sera une inversion.

   2a. accumuler le nombre d'inversions dans la variable de compteur num_inversions.

   2b. supprimer A[1] du tableau A et également de sa position correspondante dans le tableau B

3. reprendre l'étape 2 jusqu'à ce qu'il n'y ait plus d'éléments dans A.

Voici un exemple d'exécution de cet algorithme. Tableau original A = (6, 9, 1, 14, 8, 12, 3, 2)

1 : Fusionner le tri et copier dans le tableau B

B = (1, 2, 3, 6, 8, 9, 12, 14)

2 : Prendre A[1] et faire une recherche binaire pour le trouver dans le tableau B

A[1] = 6

B = (1, 2, 3, 6 , 8, 9, 12, 14)

Le 6 est en 4ème position du tableau B, il y a donc 3 inversions. Nous le savons parce que 6 était en première position dans le tableau A, donc tout élément de valeur inférieure qui apparaîtrait ensuite dans le tableau A aurait un indice de j > i (puisque i dans ce cas est 1).

2.b : Retirer A[1] du tableau A et aussi de sa position correspondante dans le tableau B (les éléments en gras sont retirés).

A = ( 6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)

3 : Ré-exécutez l'étape 2 sur les nouvelles matrices A et B.

A[1] = 9

B = (1, 2, 3, 8, 9, 12, 14)

Le 9 est maintenant en 5ème position du tableau B, il y a donc 4 inversions. Nous le savons parce que 9 était en première position dans le tableau A, donc tout élément de valeur inférieure qui apparaîtrait par la suite aurait un indice de j > i (puisque i dans ce cas est à nouveau 1). Retirez A[1] du tableau A et également de sa position correspondante dans le tableau B (les éléments en gras sont retirés).

A = ( 9 , 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 8, 9 , 12, 14) = (1, 2, 3, 8, 12, 14)

En continuant dans cette voie, nous obtiendrons le nombre total d'inversions pour le tableau A une fois la boucle terminée.

L'étape 1 (tri par fusion) s'exécute en O(n * log n). L'étape 2 s'exécuterait n fois et, à chaque exécution, effectuerait une recherche binaire qui prendrait O(log n) pour s'exécuter, soit un total de O(n * log n). Le temps d'exécution total serait donc de O(n * log n) + O(n * log n) = O(n * log n).

Merci pour votre aide. Le fait d'écrire les tableaux d'échantillons sur une feuille de papier m'a vraiment aidé à visualiser le problème.

Answer 3

Le seul conseil que je pourrais donner à ce sujet (qui ressemble étrangement à une question de devoir ;) ) est de le faire d'abord manuellement avec un petit ensemble de nombres (par exemple 5), puis de noter les étapes que vous avez suivies pour résoudre le problème.

Cela devrait vous permettre de trouver une solution générique que vous pourrez utiliser pour écrire le code.

Answer 4

Je me demande pourquoi personne n'a mentionné arbres à indexation binaire pourtant. Vous pouvez en utiliser un pour maintenir des sommes préfixes sur les valeurs de vos éléments de permutation. Vous pouvez alors procéder de droite à gauche et compter pour chaque élément le nombre d'éléments plus petits que lui à droite :

def count_inversions(a):
  res = 0
  counts = [0]*(len(a)+1)
  rank = { v : i+1 for i, v in enumerate(sorted(a)) }
  for x in reversed(a):
    i = rank[x] - 1
    while i:
      res += counts[i]
      i -= i & -i
    i = rank[x]
    while i <= len(a):
      counts[i] += 1
      i += i & -i
  return res

La complexité est O(n log n), et le facteur constant est très faible.

Answer 5

En Python

# O(n log n)

def count_inversion(lst):
    return merge_count_inversion(lst)[1]

def merge_count_inversion(lst):
    if len(lst) <= 1:
        return lst, 0
    middle = int( len(lst) / 2 )
    left, a = merge_count_inversion(lst[:middle])
    right, b = merge_count_inversion(lst[middle:])
    result, c = merge_count_split_inversion(left, right)
    return result, (a + b + c)

def merge_count_split_inversion(left, right):
    result = []
    count = 0
    i, j = 0, 0
    left_len = len(left)
    while i < left_len and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            count += left_len - i
            j += 1
    result += left[i:]
    result += right[j:]
    return result, count        

#test code
input_array_1 = []  #0
input_array_2 = [1] #0
input_array_3 = [1, 5]  #0
input_array_4 = [4, 1] #1
input_array_5 = [4, 1, 2, 3, 9] #3
input_array_6 = [4, 1, 3, 2, 9, 5]  #5
input_array_7 = [4, 1, 3, 2, 9, 1]  #8

print count_inversion(input_array_1)
print count_inversion(input_array_2)
print count_inversion(input_array_3)
print count_inversion(input_array_4)
print count_inversion(input_array_5)
print count_inversion(input_array_6)
print count_inversion(input_array_7)