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

J'ai récemment dû faire cela en R :

inversionNumber <- function(x){
    mergeSort <- function(x){
        if(length(x) == 1){
            inv <- 0
        } else {
            n <- length(x)
            n1 <- ceiling(n/2)
            n2 <- n-n1
            y1 <- mergeSort(x[1:n1])
            y2 <- mergeSort(x[n1+1:n2])
            inv <- y1$inversions + y2$inversions
            x1 <- y1$sortedVector
            x2 <- y2$sortedVector
            i1 <- 1
            i2 <- 1
            while(i1+i2 <= n1+n2+1){
                if(i2 > n2 || i1 <= n1 && x1[i1] <= x2[i2]){
                    x[i1+i2-1] <- x1[i1]
                    i1 <- i1 + 1
                } else {
                    inv <- inv + n1 + 1 - i1
                    x[i1+i2-1] <- x2[i2]
                    i2 <- i2 + 1
                }
            }
        }
        return (list(inversions=inv,sortedVector=x))
    }
    r <- mergeSort(x)
    return (r$inversions)
}

Answer 2

Mise en œuvre de Java :

import java.lang.reflect.Array;
import java.util.Arrays;

public class main {

public static void main(String[] args) {
    int[] arr = {6, 9, 1, 14, 8, 12, 3, 2};
    System.out.println(findinversion(arr,0,arr.length-1));
}

public static int findinversion(int[] arr,int beg,int end) {
    if(beg >= end)
        return 0;

    int[] result = new int[end-beg+1];
    int index = 0;
    int mid = (beg+end)/2;
    int count = 0, leftinv,rightinv;
    //System.out.println("...."+beg+"   "+end+"  "+mid);
    leftinv = findinversion(arr, beg, mid);
    rightinv = findinversion(arr, mid+1, end);
    l1:
    for(int i = beg, j = mid+1; i<=mid || j<=end;/*index < result.length;*/ ) {
        if(i>mid) {
            for(;j<=end;j++)
                result[index++]=arr[j];
            break l1;
        }
        if(j>end) {
            for(;i<=mid;i++)
                result[index++]=arr[i];
            break l1;
        }
        if(arr[i] <= arr[j]) {
            result[index++]=arr[i];
            i++;    
        } else {
            System.out.println(arr[i]+"  "+arr[j]);
            count = count+ mid-i+1;
            result[index++]=arr[j];
            j++;    
        }
    }

    for(int i = 0, j=beg; i< end-beg+1; i++,j++)
        arr[j]= result[i];
    return (count+leftinv+rightinv);
    //System.out.println(Arrays.toString(arr));
}

}

Answer 3

Voici mon point de vue en utilisant Scala :

trait MergeSort {
  def mergeSort(ls: List[Int]): List[Int] = {
    def merge(ls1: List[Int], ls2: List[Int]): List[Int] =
      (ls1, ls2) match {
        case (_, Nil) => ls1
        case (Nil, _) => ls2
        case (lowsHead :: lowsTail, highsHead :: highsTail) =>
          if (lowsHead <= highsHead) lowsHead :: merge(lowsTail, ls2)
          else highsHead :: merge(ls1, highsTail)
      }

    ls match {
      case Nil => Nil
      case head :: Nil => ls
      case _ =>
        val (lows, highs) = ls.splitAt(ls.size / 2)
        merge(mergeSort(lows), mergeSort(highs))
    }
  }
}

object InversionCounterApp extends App with MergeSort {
  @annotation.tailrec
  def calculate(list: List[Int], sortedListZippedWithIndex: List[(Int, Int)], counter: Int = 0): Int =
    list match {
      case Nil => counter
      case head :: tail => calculate(tail, sortedListZippedWithIndex.filterNot(_._1 == 1), counter + sortedListZippedWithIndex.find(_._1 == head).map(_._2).getOrElse(0))
    }

  val list: List[Int] = List(6, 9, 1, 14, 8, 12, 3, 2)
  val sortedListZippedWithIndex: List[(Int, Int)] = mergeSort(list).zipWithIndex
  println("inversion counter = " + calculate(list, sortedListZippedWithIndex))
  // prints: inversion counter = 28 
}

Answer 4

Le code C est facile à comprendre :

#include<stdio.h>
#include<stdlib.h>

//To print an array
void print(int arr[],int n)
{
    int i;
    for(i=0,printf("\n");i<n;i++)
        printf("%d ",arr[i]);
    printf("\n");
}

//Merge Sort
int merge(int arr[],int left[],int right[],int l,int r)
{
    int i=0,j=0,count=0;
    while(i<l || j<r)
    {
        if(i==l)
        {
            arr[i+j]=right[j];
            j++;
        }
        else if(j==r)
        {
            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+=l-i;
            j++;
        }
    }
    //printf("\ncount:%d\n",count);
    return count;
}

//Inversion Finding
int inversions(int arr[],int high)
{
    if(high<1)
        return 0;

    int mid=(high+1)/2;
    int left[mid];
    int right[high-mid+1];

    int i,j;
    for(i=0;i<mid;i++)
        left[i]=arr[i];

    for(i=high-mid,j=high;j>=mid;i--,j--)
        right[i]=arr[j];

    //print(arr,high+1);
    //print(left,mid);
    //print(right,high-mid+1);

    return inversions(left,mid-1) + inversions(right,high-mid) + merge(arr,left,right,mid,high-mid+1);

}
int main()
{
    int arr[]={6,9,1,14,8,12,3,2};
    int n=sizeof(arr)/sizeof(arr[0]);
    print(arr,n);
    printf("%d ",inversions(arr,n-1));
    return 0;
}

Answer 5

Une autre solution Python

def inv_cnt(a):
n = len(a)
if n==1:
    return a,0
left = a[0:n//2] # should be smaller
left,cnt1 = inv_cnt(left)    
right = a[n//2:] # should be larger
right, cnt2 = inv_cnt(right)

cnt = 0    
i_left = i_right = i_a = 0
while i_a < n:
    if (i_right>=len(right)) or (i_left < len(left) and left[i_left] <= right[i_right]):
        a[i_a] = left[i_left]
        i_left += 1
    else:
        a[i_a] = right[i_right]
        i_right += 1              
        if i_left < len(left):
            cnt += len(left) - i_left        
    i_a += 1    

return (a, (cnt1 + cnt2 + cnt))