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 ma solution O(n log n) en Ruby :

def solution(t)
    sorted, inversion_count = sort_inversion_count(t)
    return inversion_count
end

def sort_inversion_count(t)
    midpoint = t.length / 2
    left_half = t[0...midpoint]
    right_half = t[midpoint..t.length]

    if midpoint == 0
        return t, 0
    end

    sorted_left_half, left_half_inversion_count = sort_inversion_count(left_half)
    sorted_right_half, right_half_inversion_count = sort_inversion_count(right_half)

    sorted = []
    inversion_count = 0
    while sorted_left_half.length > 0 or sorted_right_half.length > 0
        if sorted_left_half.empty?
            sorted.push sorted_right_half.shift
        elsif sorted_right_half.empty?
            sorted.push sorted_left_half.shift
        else
            if sorted_left_half[0] > sorted_right_half[0]
                inversion_count += sorted_left_half.length
                sorted.push sorted_right_half.shift
            else
                sorted.push sorted_left_half.shift
            end
        end
    end

    return sorted, inversion_count + left_half_inversion_count + right_half_inversion_count
end

Et quelques cas de test :

require "minitest/autorun"

class TestCodility < Minitest::Test
    def test_given_example
        a = [-1, 6, 3, 4, 7, 4]
        assert_equal solution(a), 4
    end

    def test_empty
        a = []
        assert_equal solution(a), 0
    end

    def test_singleton
        a = [0]
        assert_equal solution(a), 0
    end

    def test_none
        a = [1,2,3,4,5,6,7]
        assert_equal solution(a), 0
    end

    def test_all
        a = [5,4,3,2,1]
        assert_equal solution(a), 10
    end

    def test_clones
        a = [4,4,4,4,4,4]
        assert_equal solution(a), 0
    end
end

Answer 2

La meilleure façon de l'optimiser sera de le résoudre par un tri par fusion où, lors de la fusion, nous pouvons vérifier combien d'inversions sont nécessaires en comparant les tableaux de gauche et de droite. Si l'élément du tableau de gauche est plus grand que celui du tableau de droite, il y aura inversion.

Approche du tri par fusion :-

Voici le code . Le code est exactement le même que celui du tri par fusion, à l'exception de l'extrait de code sous le nom de mergeToParent méthode où je compte l'inversion sous une autre condition de (left[leftunPicked] < right[rightunPicked])

public class TestInversionThruMergeSort {

    static int count =0;

    public static void main(String[] args) {
        int[] arr = {6, 9, 1, 14, 8, 12, 3, 2};

        partition(arr);

        for (int i = 0; i < arr.length; i++) {

            System.out.println(arr[i]);
        }

        System.out.println("inversions are "+count);

    }

    public static void partition(int[] arr) {

        if (arr.length > 1) {

            int mid = (arr.length) / 2;
            int[] left = null;

            if (mid > 0) {
                left = new int[mid];

                for (int i = 0; i < mid; i++) {
                    left[i] = arr[i];
                }
            }

            int[] right = new int[arr.length - left.length];

            if ((arr.length - left.length) > 0) {
                int j = 0;
                for (int i = mid; i < arr.length; i++) {
                    right[j] = arr[i];
                    ++j;
                }
            }

            partition(left);
            partition(right);
            mergeToParent(left, right, arr);
        }

    }

    public static void mergeToParent(int[] left, int[] right, int[] parent) {

        int leftunPicked = 0;
        int rightunPicked = 0;
        int parentIndex = -1;

        while (rightunPicked < right.length && leftunPicked < left.length) {

            if (left[leftunPicked] < right[rightunPicked]) {
                parent[++parentIndex] = left[leftunPicked];
                ++leftunPicked;

            } else {
                count = count + left.length-leftunPicked;
                if ((rightunPicked < right.length)) {
                    parent[++parentIndex] = right[rightunPicked];
                    ++rightunPicked;
                }
            }

        }

        while (leftunPicked < left.length) {
            parent[++parentIndex] = left[leftunPicked];
            ++leftunPicked;
        }

        while (rightunPicked < right.length) {
            parent[++parentIndex] = right[rightunPicked];
            ++rightunPicked;
        }

    }

}

Une autre approche où nous pouvons comparer le tableau d'entrée avec le tableau trié : -. Cette mise en œuvre de la réponse Diablo. Bien que cette approche ne soit pas à privilégier, car retirer les n éléments d'un tableau ou d'une liste est log(n^2).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class TestInversion {

    public static void main(String[] args) {

        Integer [] arr1 = {6, 9, 1, 14, 8, 12, 3, 2};

        List<Integer> arr = new ArrayList(Arrays.asList(arr1));
        List<Integer> sortArr = new ArrayList<Integer>();

        for(int i=0;i<arr.size();i++){
            sortArr.add(arr.get(i));

        }

        Collections.sort(sortArr);

        int inversion = 0;

        Iterator<Integer> iter = arr.iterator();

        while(iter.hasNext()){

            Integer el = (Integer)iter.next();
            int index = sortArr.indexOf(el);

            if(index+1 > 1){
                inversion = inversion + ((index+1)-1);
            }

            //iter.remove();
            sortArr.remove(el);

        }

        System.out.println("Inversions are "+inversion);

    }

}

Answer 3

Nombre maximum d'inversions possibles pour une liste de taille n pourrait être généralisé par une expression :

maxPossibleInversions = (n * (n-1) ) / 2

Ainsi, pour un tableau de taille 6 le maximum d'inversions possibles sera égal à 15 .

Pour atteindre une complexité de n logn on pourrait greffer l'algorithme d'inversion sur le tri par fusion.

Voici les étapes générales :

• Divisez le tableau en deux
• Appelez la routine mergeSort. Si l'élément dans le sous tableau de gauche est plus grand que l'élément dans le sous tableau de droite faire inversionCount += leftSubArray.length

C'est ça !

Il s'agit d'un exemple simple, que j'ai réalisé en utilisant Javascript :

var arr = [6,5,4,3,2,1]; // Sample input array

var inversionCount = 0;

function mergeSort(arr) {
    if(arr.length == 1)
        return arr;

    if(arr.length > 1) {
        let breakpoint = Math.ceil((arr.length/2));
        // Left list starts with 0, breakpoint-1
        let leftList = arr.slice(0,breakpoint);
        // Right list starts with breakpoint, length-1
        let rightList = arr.slice(breakpoint,arr.length);

        // Make a recursive call
        leftList = mergeSort(leftList);
        rightList = mergeSort(rightList);

        var a = merge(leftList,rightList);
        return a;
    }
}

function merge(leftList,rightList) {
    let result = [];
    while(leftList.length && rightList.length) {
        /**
         * The shift() method removes the first element from an array
         * and returns that element. This method changes the length
         * of the array.
         */
        if(leftList[0] <= rightList[0]) {
            result.push(leftList.shift());
        }else{
            inversionCount += leftList.length;
            result.push(rightList.shift());
        }
    }

    while(leftList.length)
        result.push(leftList.shift());

    while(rightList.length)
        result.push(rightList.shift());

    console.log(result);
    return result;
}

mergeSort(arr);
console.log('Number of inversions: ' + inversionCount);

Answer 4

Implémentation du comptage des inversions dans un tableau avec le tri par fusion en Swift :

Notez que le nombre de swaps est incrémenté par

nSwaps += mid + 1 - iL 

(qui est la longueur relative du côté gauche du tableau moins l'index de l'élément actuel dans le côté gauche)

... car c'est le nombre d'éléments que l'élément de droite du tableau a dû sauter (# d'inversions) pour être trié.

func merge(arr: inout [Int], arr2: inout [Int], low: Int, mid: Int, high: Int) -> Int {
    var nSwaps = 0;

    var i = low;
    var iL = low;
    var iR = mid + 1;

    while iL <= mid && iR <= high {
        if arr2[iL] <= arr2[iR] {
            arr[i] = arr2[iL]
            iL += 1
            i += 1
        } else {
            arr[i] = arr2[iR]
            nSwaps += mid + 1 - iL
            iR += 1
            i += 1
        }
    }

    while iL <= mid {
        arr[i] = arr2[iL]
        iL += 1
        i += 1
    }

    while iR <= high {
        arr[i] = arr2[iR]
        iR += 1
        i += 1
    }

    return nSwaps
}

func mergeSort(arr: inout [Int]) -> Int {
    var arr2 = arr
    let nSwaps = mergeSort(arr: &arr, arr2: &arr2, low: 0, high: arr.count-1)
    return nSwaps
}

func mergeSort(arr: inout [Int], arr2: inout [Int], low: Int, high: Int) -> Int {

    if low >= high {
        return 0
    }

    let mid = low + ((high - low) / 2)

    var nSwaps = 0;
    nSwaps += mergeSort(arr: &arr2, arr2: &arr, low: low, high: mid)
    nSwaps += mergeSort(arr: &arr2, arr2: &arr, low: mid+1, high: high)
    nSwaps += merge(arr: &arr, arr2: &arr2, low: low, mid: mid, high: high)

    return nSwaps
}

var arrayToSort: [Int] = [2, 1, 3, 1, 2]
let nSwaps = mergeSort(arr: &arrayToSort)

print(arrayToSort) // [1, 1, 2, 2, 3]
print(nSwaps) // 4

Answer 5

Utilise mergesort, dans l'étape de fusion incrémente le compteur si le nombre copié en sortie provient du tableau de droite.