Инверсии подмассивов

Опубликовано: 25 Января, 2022

У нас есть массив A из n целых чисел, который мы планируем отсортировать. В частности, мы хотим знать, насколько близок массив к сортировке. Для этого мы вводим идею инверсии . Инверсия в массиве - это пара двух индексов i и j, таких что i < j и A [i] > A [j] . Если наш массив содержит одну инверсию, нам нужно только поменять местами A [i] и A [j] , чтобы отсортировать массив. По определению сортируется массив, содержащий 0 инверсий.

Проблема: для массива A из n целых чисел найдите сумму числа инверсий во всех подмассивах длины k . Чтобы уточнить, нужно определить количество инверсий в каждом из n - k + 1 подмассивов длины k и сложить их.
Входные данные: первая строка содержит два целых числа n и k, разделенных пробелом. Следующая строка содержит последовательность из n целых чисел, разделенных пробелом, где i- е целое число в последовательности - A [i] .
Примеры:

 Ввод: arr [] = {1 2 3 4 5 6}
        k = 2
Выход: 0

Ввод: arr [] = {1 6 7 2}
        k = 3
Выход: 2
Есть два подмассива размера 3,
{1, 6, 7} и {6, 7, 2}. Количество
инверсии в первом подмассиве 0
и подсчет инверсий в секунду
подмассив равен 2. Итак, сумма равна 0 + 2 = 2

Ввод: 8 4
12 3 14 8 15 1 4 22
Выход: 14

Ввод: 10 5
15 51 44 44 76 50 29 88 48 50
Выход: 25
Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

[1] Наивный подход
Поначалу эта проблема кажется довольно тривиальной, и мы можем легко реализовать наивный алгоритм, чтобы ее решение было перебором. Мы просто создаем окно длиной k и прокручиваем окно вдоль A , добавляя количество инверсий в окне на каждой итерации. Чтобы найти количество инверсий, самый простой подход - использовать два цикла for для рассмотрения всех пар элементов и увеличивать счетчик, если пара образует инверсию.

This approach is very easy to implement, but is it efficient? Let’s analyze the algorithm. The outermost loop runs n – k + 1 times, once for each k-subarray of A. At each of these iterations, we find the number of inversions in the window. To do this, we consider element 1 and elements 2, …, n, then element 2 and elements 3, …, n until element n – 1 and element n. Effectively, we’re performing n + (n – 1) + (n – 2) + … + 1 = n(n + 1)/2 operations. Thus, our algorithm performs approximately (n – k + 1)(n)(n + 1)/2 operations which is O(n^3 – kn^2). Since k can range from 1 to n, the worst case performance for this algorithm is O(n^3) when k = n/2. We can do better! 

C++

// C++ implementation of above approach
#include <iostream>
using namespace std;
 
// Helper function, counts number of inversions
// via bubble sort loop
int bubble_count(int arr[], int start, int end)
{
    int count = 0;
    for (int i = start; i < end; i++)
    {
        for (int j = i + 1; j < end; j++)
        {
            if (arr[i] > arr[j])
            {
                count++;
            }
        }
    }
    return count;
}
 
// Inversion counting method, slides window of
// [start, end] across array
int inversion_count(int n, int k, int a[])
{
    int count = 0;
    for (int start = 0; start < n - k + 1; start++)
    {
        int end = start + k;
        count += bubble_count(a, start, end);
    }
    return count;
}
 
// Driver Code
int main()
{
    int n = 10;
    int arr[n] = { 15, 51, 44, 44, 76,
                   50, 29, 88, 48, 50 };
    int k = 5;
     
    int result = inversion_count(n, k, arr);
    cout << result;
    return 0;
}
 
// This code is contributed by PrinciRaj1992

Java

public class Subarray_Inversions {
 
    // Inversion counting method, slides window of [start,
    // end] across array
    static int inversion_count(int n, int k, int[] a)
    {
        int count = 0;
        for (int start = 0; start < n - k + 1; start++) {
            int end = start + k;
            count += bubble_count(a, start, end);
        }
        return count;
    }
 
    // Helper function, counts number of inversions via
    // bubble sort loop
    public static int bubble_count(int[] arr, int start, int end)
    {
        int count = 0;
        for (int i = start; i < end; i++) {
            for (int j = i + 1; j < end; j++) {
                if (arr[i] > arr[j]) {
                    count++;
                }
            }
        }
        return count;
    }
 
    public static void main(String[] args)
    {
        int n = 10;
        int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
        int k = 5;
 
        long result = inversion_count(n, k, arr);
        System.out.println(result);
    }
}

Python3

# Python3 implementation of above approach
 
# Helper function, counts number of inversions
# via bubble sort loop
def bubble_count(arr, start, end):
    count = 0;
    for i in range(start, end):
 
        for j in range(i + 1, end):
 
            if (arr[i] > arr[j]):
                count += 1;
 
    return count;
 
# Inversion counting method, slides window
# of [start, end] across array
def inversion_count(n, k, a):
    count = 0;
    for start in range(0, n - k + 1):
        end = start + k;
        count += bubble_count(a, start, end);
 
    return count;
 
# Driver Code
if __name__ == "__main__":
    n = 10;
    arr = [15, 51, 44, 44, 76,
           50, 29, 88, 48, 50];
    k = 5;
 
    result = inversion_count(n, k, arr);
    print(result);
 
# This code is contributed by Rajput-Ji

C#

// C# implementation of above approach
using System;
 
public class Subarray_Inversions
{
 
    // Inversion counting method, slides window of [start,
    // end] across array
    static int inversion_count(int n, int k, int[] a)
    {
        int count = 0;
        for (int start = 0; start < n - k + 1; start++)
        {
            int end = start + k;
            count += bubble_count(a, start, end);
        }
        return count;
    }
 
    // Helper function, counts number of inversions via
    // bubble sort loop
    public static int bubble_count(int[] arr, int start, int end)
    {
        int count = 0;
        for (int i = start; i < end; i++)
        {
            for (int j = i + 1; j < end; j++)
            {
                if (arr[i] > arr[j])
                {
                    count++;
                }
            }
        }
        return count;
    }
 
    // Driver code
    public static void Main()
    {
        int n = 10;
        int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
        int k = 5;
 
        long result = inversion_count(n, k, arr);
        Console.WriteLine(result);
    }
}
 
// This code is contributed by Rajput-Ji

Выход:

 25

[2] Mergesort-based Implementation
One optimization we can make is improving our inefficient, quadratic-time inversion counting method. One approach could involve using a mergesort-based method as outlined in this article. Since this runs in O(nlogn), our overall runtime is reduced to O(n^2logn), which is better, but still won’t be able to handle cases for which n = 10^6 for instance.  

Java

import java.util.*;
 
public class Subarray_Inversions {
 
    // Inversion counting method, slides window of [start,
    // end] across array
    static int inversion_count(int n, int k, int[] a)
    {
        int count = 0;
        for (int start = 0; start < n - k + 1; start++) {
            int[] sub_array = new int[k];
            for (int i = start; i < start + k; i++) {
                sub_array[i - start] = a[i];
            }
            count += subarray_inversion_count(sub_array);
        }
        return count;
    }
 
    // Counts number of inversions when merging
    public static long merge_inversion_count(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;
    }
 
    // Divide and conquer approach -- splits array and counts
    // inversions via merge method
    public static long subarray_inversion_count(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 subarray_inversion_count(left) +
               subarray_inversion_count(right) +
               merge_inversion_count(arr, left, right);
    }
 
    public static void main(String[] args)
    {
        int n = 10;
        int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
        int k = 5;
 
        long result = inversion_count(n, k, arr);
        System.out.println(result);
    }
}

C#

using System;
using System.Collections.Generic;
 
  
public class Subarray_Inversions {
  
    // Inversion counting method, slides window of [start,
    // end] across array
    static int inversion_count(int n, int k, int[] a)
    {
        int count = 0;
        for (int start = 0; start < n - k + 1; start++) {
            int[] sub_array = new int[k];
            for (int i = start; i < start + k; i++) {
                sub_array[i - start] = a[i];
            }
            count += subarray_inversion_count(sub_array);
        }
        return count;
    }
  
    // Counts number of inversions when merging
    public static int merge_inversion_count(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;
    }
  
    // Divide and conquer approach -- splits array and counts
    // inversions via merge method
    public static int subarray_inversion_count(int[] arr)
    {
        if (arr.Length < 2)
            return 0;
  
        int m = (arr.Length + 1) / 2;
        int []left = new int[m];
        Array.Copy(arr, 0, left,0, m);
        int []right = new int[arr.Length - m];
        Array.Copy(arr, m, right,0, arr.Length - m);
  
        return subarray_inversion_count(left) +
               subarray_inversion_count(right) +
               merge_inversion_count(arr, left, right);
    }
  
    public static void Main(String[] args)
    {
        int n = 10;
        int[] arr = { 15, 51, 44, 44, 76, 50, 29, 88, 48, 50 };
        int k = 5;
  
        long result = inversion_count(n, k, arr);

РЕКОМЕНДУЕМЫЕ СТАТЬИ