calculating the number of “inversions” in a permutation

Question

Let A be an array of size N. we call a couple of indexes (i,j) an "inverse" if i < j and A[i] > A[j]

I need to find an algorithm that receives an array of size N (with unique numbers) and return the number of inverses in time of O(n*log(n)).

Solution 1

You can use the merge sort algorithm.

In the merge algorithm's loop, the left and right halves are both sorted ascendingly, and we want to merge them into a single sorted array. Note that all the elements in the right side have higher indexes than those in the left side.

Assume array[leftIndex] > array[rightIndex]. This means that all elements in the left part following the element with index leftIndex are also larger than the current one in the right side (because the left side is sorted ascendingly). So the current element in the right side generates numberOfElementsInTheLeftSide - leftIndex + 1 inversions, so add this to your global inversion count.

Once the algorithm finishes executing you have your answer, and merge sort is O(n log n) in the worst case.

Solution 2

There is an article published in SIAM in 2010 by Cham and Patrascu entitled Counting Inversions, Offline Orthogonal Range Counting, and Related Problems that gives an algorithm taking O(n sqrt(log(n))) time. This is currently the best known algorithm, and improves the long-standing O(n log(n) / log(log(n))) algorithm. From the abstract:

We give an O(n sqrt(lg n))-time algorithm for counting the number of inversions in a permutation on n elements. This improves a long-standing previous bound of O(n lg n / lg lg n) that followed from Dietz's data structure [WADS'89], and answers a question of Andersson and Petersson [SODA'95]. As Dietz's result is known to be optimal for the related dynamic rank problem, our result demonstrates a significant improvement in the offline setting.

Our new technique is quite simple: we perform a "vertical partitioning" of a trie (akin to van Emde Boas trees), and use ideas from external memory. However, the technique finds numerous applications: for example, we obtain

• in d dimensions, an algorithm to answer n offline orthogonal range counting queries in time O(n lg^d-2+1/d n);
• an improved construction time for online data structures for orthogonal range counting;
• an improved update time for the partial sums problem;
• faster Word RAM algorithms for finding the maximum depth in an arrangement of axis-aligned rectangles, and for the slope selection problem.

As a bonus, we also give a simple (1 + ε)-approximation algorithm for counting inversions that runs in linear time, improving the previous O(n lg lg n) bound by Andersson and Petersson.

Solution 3

I think the awesomest way to do this (and thats just because I love the data structure) is to use a binary indexed tree. Mind you, if all you need is a solution, merge sort would work just as well (I just think this concept totally rocks!). The basic idea is this: Build a data structure which updates values in O(log n) and answers the query "How many numbers less than x have already occurred in the array so far?" Given this, you can easily answer how many are greater than x which contributes to inversions with x as the second number in the pair. For example, consider the list {3, 4, 1, 2}.

When processing 3, there's no other numbers so far, so inversions with 3 on the right side = 0 When processing 4, the number of numbers less than 4 so far = 1, thus number of greater numbers (and hence inversions) = 0 Now, when processing 1, number of numbers less than 1 = 0, this number of greater numbers = 2 which contributes to two inversions (3,1) and (4,1). Same logic applies to 2 which finds 1 number less than it and hence 2 greater than it.

Now, the only question is to understand how these updates and queries happen in log n. The url mentioned above is one of the best tutorials I've read on the subject.

Solution 4

These are the original MERGE and MERGE-SORT algorithms from Cormen, Leiserson, Rivest, Stein Introduction to Algorithms:

MERGE(A,p,q,r)
 1  n1 = q - p + 1
 2  n2 = r - q
 3  let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
 4  for i = 1 to n1
 5      L[i] = A[p + i - 1]
 6  for j = 1 to n2
 7      R[j] = A[q + j]
 8  L[n1 + 1] = infinity
 9  R[n2 + 1] = infinity
10  i = 1
11  j = 1
12  for k = p to r
13      if L[i] <= R[j] 
14          A[k] = L[i]
15          i = i + 1
16      else A[k] = R[j]
17          j = j + 1

and

MERGE-SORT(A,p,r)
 1 if p < r
 2     q = floor((p + r)/2)
 3     MERGE-SORT(A,p,q)
 4     MERGE-SORT(A,q + 1,r)
 5     MERGE(A,p,q,r)

at line 8 and 9 in MERGE infinity is the so called sentinel card, which has such value that all array elements are smaller then it. To get the number of inversion one can introduce a global counter, let's say ninv initialized to zero before calling MERGE-SORT and than to modify the MERGE algorithm by adding one line in the else statement after line 16, something like

ninv += n1 - i

than after MERGE-SORT is finished ninv will hold the number of inversions

View more solutions

Comments

[Steve Jessop]

Very similar: stackoverflow.com/questions/4552591/…. The difference is that this specifies the array contains a permutation, as opposed to arbitrary values.

[PengOne]

Also related: Counting inversions in an array