Counting Inversions between 2 arrays

Question

I am looking for an algorithm to solve this problem:

Given 2 arrays, A and B which are both permutations of [1..n], what is the number of inversions between these 2?

An inversion here would be when a pair elements (i,j) this holds:

if A.indexOf(i) > A.indexOf(j) && B.indexOf(i) < B.indexOf(j)

or

if A.indexOf(i) < A.indexOf(j) && B.indexOf(i) > B.indexOf(j)

I know that there exist multiple ways to do this when you can assume the first array is sorted, like counting the inversions while doing MergeSort, but I have 2 non-sorted arrays.

Example:

A = [6,3,4,1,2,5] and B = [3,5,2,6,1,4]
No. of inversions = 9
6 has a lower index than 3 in A, but a higher index than 3 in B. This is an inversion.

I am hoping to achieve this in O(n log n) time complexity using a Divide and Conquer approach.

Why did you remove your other question about Implementing Breath First Search with OpenCL? — VMAtm
I contacted my teacher and I already got the solution thanks to him, so I felt the question was no longer needed here. — van Leemhuyzen
It's better to introduce your own answer for a future visitors rather than delete a good question. — VMAtm

h8red h8red · Accepted Answer · 2016-03-11T16:04:38

In order to do this, we can make a simple substitution (taken from your example): 6->1, 3->2, 4->3, 1->4, 2->5, 5->6. Thus, the first list becomes [1,2,3,4,5,6] and the second becomes [2,6,5,1,4,3]. Then, we can run a simple O(n log n) algorithm for computing the number of inversions in the second list, which gives the answer.

This transformation can be done in O(n) operations using the additional list of indexes. ind[i] will be the index of a given number in the first list,so, if A[1]=6, then ind[6]=1.

Code for constructing the ind array:

    var A = new List<int> {6, 3, 4, 1, 2, 5};
    foreach (var num in A) Console.Write(num + " ");
    Console.WriteLine("");

    var indexes = new int[7];
    for (var i = 0; i < 6; ++i)
        indexes[A[i]] = i + 1;

    for (var i = 1; i < 7; ++i) Console.Write(indexes[i] + " ");
    Console.WriteLine("");

Then, given this array (in the case of this example [4,5,2,3,6,1]) we can make the substitution using resultArray[i] = ind[B[i]];

Code for constructing the substituted array:

    var B = new List<int> {3, 5, 2, 6, 1, 4};

    var resultList = new List<int>();
    for (var i = 0; i < 6; ++i)
        resultList.Add(indexes[B[i]]);

    for(var i = 0; i < 6; ++i)
        Console.Write(resultList[i] + " ");

Then we can just run the algorithm for computing the permutations in the last array, which will be the answer. (I can give the code for computing permutations in O(n log n), but i think that was not the problem here).

Counting Inversions between 2 arrays

2 Answers