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 une implémentation O(n*log(n)) en perl :

sub sort_and_count {
    my ($arr, $n) = @_;
    return ($arr, 0) unless $n > 1;

    my $mid = $n % 2 == 1 ? ($n-1)/2 : $n/2;
    my @left = @$arr[0..$mid-1];
    my @right = @$arr[$mid..$n-1];

    my ($sleft, $x) = sort_and_count( \@left, $mid );
    my ($sright, $y) = sort_and_count( \@right, $n-$mid);
    my ($merged, $z) = merge_and_countsplitinv( $sleft, $sright, $n );

    return ($merged, $x+$y+$z);
}

sub merge_and_countsplitinv {
    my ($left, $right, $n) = @_;

    my ($l_c, $r_c) = ($#$left+1, $#$right+1);
    my ($i, $j) = (0, 0);
    my @merged;
    my $inv = 0;

    for my $k (0..$n-1) {
        if ($i<$l_c && $j<$r_c) {
            if ( $left->[$i] < $right->[$j]) {
                push @merged, $left->[$i];
                $i+=1;
            } else {
                push @merged, $right->[$j];
                $j+=1;
                $inv += $l_c - $i;
            }
        } else {
            if ($i>=$l_c) {
                push @merged, @$right[ $j..$#$right ];
            } else {
                push @merged, @$left[ $i..$#$left ];
            }
            last;
        }
    }

    return (\@merged, $inv);
}

Answer 2

Ma réponse en Python :

1- Triez d'abord le tableau et faites-en une copie. Dans mon programme, B représente le tableau trié. 2- Itérer sur le tableau original (non trié), et trouver l'index de cet élément sur la liste triée. Notez également l'indice de l'élément. 3- Vérifiez que l'élément n'a pas de doublons, si c'est le cas, vous devez changer la valeur de votre index par -1. C'est exactement ce que fait la condition "while" de mon programme. 4- Continuez à compter l'inversion qui fera la valeur de votre index, et supprimez l'élément une fois que vous avez calculé son inversion.

def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False

    while first <= last and not found:
        midpoint = (first + last)//2
        if alist[midpoint] == item:
            return midpoint
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1

def solution(A):

    B = list(A)
    B.sort()
    inversion_count = 0
    for i in range(len(A)):
        j = binarySearch(B, A[i])
        while B[j] == B[j - 1]:
            if j < 1:
                break
            j -= 1

        inversion_count += j
        B.pop(j)

    if inversion_count > 1000000000:
        return -1
    else:
        return inversion_count

print solution([4, 10, 11, 1, 3, 9, 10])

Answer 3

J'ai une autre solution, mais je crains qu'elle ne fonctionne que pour des éléments de tableau distincts.

//Code
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int i,n;
    cin >> n;
    int arr[n],inv[n];
    for(i=0;i<n;i++){
        cin >> arr[i];
    }
    vector<int> v;
    v.push_back(arr[n-1]);
    inv[n-1]=0;
    for(i=n-2;i>=0;i--){
        auto it = lower_bound(v.begin(),v.end(),arr[i]); 
        //calculating least element in vector v which is greater than arr[i]
        inv[i]=it-v.begin();
        //calculating distance from starting of vector
        v.insert(it,arr[i]);
        //inserting that element into vector v
    }
    for(i=0;i<n;i++){
        cout << inv[i] << " ";
    }
    cout << endl;
    return 0;
}

Pour expliquer mon code, nous continuons à ajouter des éléments à partir de l'extrémité du tableau. indice du premier élément du vecteur v qui est plus grand que notre élément entrant Après cela, nous insérons cet élément dans le vecteur v à sa position correcte de sorte que le vecteur v reste dans l'ordre trié.

//INPUT     
4
2 1 4 3

//OUTPUT    
1 0 1 0

//To calculate total inversion count just add up all the elements in output array

Answer 4

Une solution possible en C++ satisfaisant l'exigence de complexité temporelle O(N*log(N)) serait la suivante.

#include <algorithm>

vector<int> merge(vector<int>left, vector<int>right, int &counter)
{

    vector<int> result;

    vector<int>::iterator it_l=left.begin();
    vector<int>::iterator it_r=right.begin();

    int index_left=0;

    while(it_l!=left.end() || it_r!=right.end())
    {

        // the following is true if we are finished with the left vector 
        // OR if the value in the right vector is the smaller one.

        if(it_l==left.end() || (it_r!=right.end() && *it_r<*it_l) )
        {
            result.push_back(*it_r);
            it_r++;

            // increase inversion counter
            counter+=left.size()-index_left;
        }
        else
        {
            result.push_back(*it_l);
            it_l++;
            index_left++;

        }
    }

    return result;
}

vector<int> merge_sort_and_count(vector<int> A, int &counter)
{

    int N=A.size();
    if(N==1)return A;

    vector<int> left(A.begin(),A.begin()+N/2);
    vector<int> right(A.begin()+N/2,A.end());

    left=merge_sort_and_count(left,counter);
    right=merge_sort_and_count(right,counter);

    return merge(left, right, counter);

}

Il ne diffère d'un tri par fusion ordinaire que par le compteur.

Answer 5

Je pense que la réponse d'el diablo peut être optimisée pour supprimer l'étape 2b dans laquelle nous supprimons les éléments déjà traités.

Au lieu de cela, nous pouvons définir

# d'inversion pour x = position de x dans le tableau trié - position de x dans le tableau original