Advertisement
Advertisement

## Counting inversions in an array

### Question

I'm designing an algorithm to do the following: Given array `A[1... n]`, for every `i < j`, find all inversion pairs such that `A[i] > A[j]`. I'm using merge sort and copying array A to array B and then comparing the two arrays, but I'm having a difficult time seeing how I can use this to find the number of inversions. Any hints or help would be greatly appreciated.

2014/10/25
1
109
10/25/2014 9:12:20 AM

I've found it in O(n * log n) time by the following method.

1. Merge sort array A and create a copy (array B)
2. Take A and find its position in sorted array B via a binary search. The number of inversions for this element will be one less than the index number of its position in B since every lower number that appears after the first element of A will be an inversion.

2a. accumulate the number of inversions to counter variable num_inversions.

2b. remove A from array A and also from its corresponding position in array B

3. rerun from step 2 until there are no more elements in A.

Here’s an example run of this algorithm. Original array A = (6, 9, 1, 14, 8, 12, 3, 2)

1: Merge sort and copy to array B

B = (1, 2, 3, 6, 8, 9, 12, 14)

2: Take A and binary search to find it in array B

A = 6

B = (1, 2, 3, 6, 8, 9, 12, 14)

6 is in the 4th position of array B, thus there are 3 inversions. We know this because 6 was in the first position in array A, thus any lower value element that subsequently appears in array A would have an index of j > i (since i in this case is 1).

2.b: Remove A from array A and also from its corresponding position in array B (bold elements are removed).

A = (6, 9, 1, 14, 8, 12, 3, 2) = (9, 1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 6, 8, 9, 12, 14) = (1, 2, 3, 8, 9, 12, 14)

3: Rerun from step 2 on the new A and B arrays.

A = 9

B = (1, 2, 3, 8, 9, 12, 14)

9 is now in the 5th position of array B, thus there are 4 inversions. We know this because 9 was in the first position in array A, thus any lower value element that subsequently appears would have an index of j > i (since i in this case is again 1). Remove A from array A and also from its corresponding position in array B (bold elements are removed)

A = (9, 1, 14, 8, 12, 3, 2) = (1, 14, 8, 12, 3, 2)

B = (1, 2, 3, 8, 9, 12, 14) = (1, 2, 3, 8, 12, 14)

Continuing in this vein will give us the total number of inversions for array A once the loop is complete.

Step 1 (merge sort) would take O(n * log n) to execute. Step 2 would execute n times and at each execution would perform a binary search that takes O(log n) to run for a total of O(n * log n). Total running time would thus be O(n * log n) + O(n * log n) = O(n * log n).

Thanks for your help. Writing out the sample arrays on a piece of paper really helped to visualize the problem.

2008/12/03

In Python

``````# O(n log n)

def count_inversion(lst):
return merge_count_inversion(lst)

def merge_count_inversion(lst):
if len(lst) <= 1:
return lst, 0
middle = int( len(lst) / 2 )
left, a = merge_count_inversion(lst[:middle])
right, b = merge_count_inversion(lst[middle:])
result, c = merge_count_split_inversion(left, right)
return result, (a + b + c)

def merge_count_split_inversion(left, right):
result = []
count = 0
i, j = 0, 0
left_len = len(left)
while i < left_len and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
count += left_len - i
j += 1
result += left[i:]
result += right[j:]
return result, count

#test code
input_array_1 = []  #0
input_array_2 =  #0
input_array_3 = [1, 5]  #0
input_array_4 = [4, 1] #1
input_array_5 = [4, 1, 2, 3, 9] #3
input_array_6 = [4, 1, 3, 2, 9, 5]  #5
input_array_7 = [4, 1, 3, 2, 9, 1]  #8

print count_inversion(input_array_1)
print count_inversion(input_array_2)
print count_inversion(input_array_3)
print count_inversion(input_array_4)
print count_inversion(input_array_5)
print count_inversion(input_array_6)
print count_inversion(input_array_7)
``````
2013/03/01

I wonder why nobody mentioned binary-indexed trees yet. You can use one to maintain prefix sums on the values of your permutation elements. Then you can just proceed from right to left and count for every element the number of elements smaller than it to the right:

``````def count_inversions(a):
res = 0
counts = *(len(a)+1)
rank = { v : i+1 for i, v in enumerate(sorted(a)) }
for x in reversed(a):
i = rank[x] - 1
while i:
res += counts[i]
i -= i & -i
i = rank[x]
while i <= len(a):
counts[i] += 1
i += i & -i
return res
``````

The complexity is O(n log n), and the constant factor is very low.

2016/02/21

I had a question similar to this for homework actually. I was restricted that it must have O(nlogn) efficiency.

I used the idea you proposed of using Mergesort, since it is already of the correct efficiency. I just inserted some code into the merging function that was basically: Whenever a number from the array on the right is being added to the output array, I add to the total number of inversions, the amount of numbers remaining in the left array.

This makes a lot of sense to me now that I've thought about it enough. Your counting how many times there is a greater number coming before any numbers.

hth.

2009/02/12

The primary purpose of this answer is to compare the speeds of the various Python versions found here, but I also have a few contributions of my own. (FWIW, I just discovered this question while performing a duplicate search).

The relative execution speeds of algorithms implemented in CPython may be different to what one would expect from a simple analysis of the algorithms, and from experience with other languages. That's because Python provides many powerful functions and methods implemented in C that can operate on lists and other collections at close to the speed one would get in a fully-compiled language, so those operations run much faster than equivalent algorithms implemented "manually" with Python code.

Code that takes advantage of these tools can often outperform theoretically superior algorithms that try to do everything with Python operations on individual items of the collection. Of course the actual quantity of data being processed has an impact on this too. But for moderate amounts of data, code that uses an O(n²) algorithm running at C speed can easily beat an O(n log n) algorithm that does the bulk of its work with individual Python operations.

Many of the posted answers to this inversion counting question use an algorithm based on mergesort. Theoretically, this is a good approach, unless the array size is very small. But Python's built-in TimSort (a hybrid stable sorting algorithm, derived from merge sort and insertion sort) runs at C speed, and a mergesort coded by hand in Python cannot hope to compete with it for speed.

One of the more intriguing solutions here, in the answer posted by Niklas B, uses the built-in sort to determine the ranking of array items, and a Binary Indexed Tree (aka Fenwick tree) to store the cumulative sums required to calculate the inversion count. In the process of trying to understand this data structure and Niklas's algorithm I wrote a few variations of my own (posted below). But I also discovered that for moderate list sizes it's actually faster to use Python's built-in `sum` function than the lovely Fenwick tree.

``````def count_inversions(a):
total = 0
counts =  * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += sum(counts[:i])
counts[i] += 1
return total
``````

Eventually, when the list size gets around 500, the O(n²) aspect of calling `sum` inside that `for` loop rears its ugly head, and the performance starts to plummet.

Mergesort isn't the only O(nlogn) sort, and several others may be utilized to perform inversion counting. prasadvk's answer uses a binary tree sort, however his code appears to be in C++ or one of its derivatives. So I've added a Python version. I originally used a class to implement the tree nodes, but discovered that a dict is noticeably faster. I eventually used list, which is even faster, although it does make the code a little less readable.

One bonus of treesort is that it's a lot easier to implement iteratively than mergesort is. Python doesn't optimize recursion and it has a recursion depth limit (although that can be increased if you really need it). And of course Python function calls are relatively slow, so when you're trying to optimize for speed it's good to avoid function calls, when practical.

Another O(nlogn) sort is the venerable radix sort. It's big advantage is that it doesn't compare keys to each other. It's disadvantage is that it works best on contiguous sequences of integers, ideally a permutation of integers in `range(b**m)` where `b` is usually 2. I added a few versions based on radix sort after attempting to read Counting Inversions, Offline Orthogonal Range Counting, and Related Problems which is linked in calculating the number of “inversions” in a permutation.

To use radix sort effectively to count inversions in a general sequence `seq` of length n we can create a permutation of `range(n)` that has the same number of inversions as `seq`. We can do that in (at worst) O(nlogn) time via TimSort. The trick is to permute the indices of `seq` by sorting `seq`. It's easier to explain this with a small example.

``````seq = [15, 14, 11, 12, 10, 13]
b = [t[::-1] for t in enumerate(seq)]
print(b)
b.sort()
print(b)
``````

output

``````[(15, 0), (14, 1), (11, 2), (12, 3), (10, 4), (13, 5)]
[(10, 4), (11, 2), (12, 3), (13, 5), (14, 1), (15, 0)]
``````

By sorting the (value, index) pairs of `seq` we have permuted the indices of `seq` with the same number of swaps that are required to put `seq` into its original order from its sorted order. We can create that permutation by sorting `range(n)` with a suitable key function:

``````print(sorted(range(len(seq)), key=lambda k: seq[k]))
``````

output

``````[4, 2, 3, 5, 1, 0]
``````

We can avoid that `lambda` by using `seq`'s `.__getitem__` method:

``````sorted(range(len(seq)), key=seq.__getitem__)
``````

This is only slightly faster, but we're looking for all the speed enhancements we can get. ;)

The code below performs `timeit` tests on all of the existing Python algorithms on this page, plus a few of my own: a couple of brute-force O(n²) versions, a few variations on Niklas B's algorithm, and of course one based on mergesort (which I wrote without referring to the existing answers). It also has my list-based treesort code roughly derived from prasadvk's code, and various functions based on radix sort, some using a similar strategy to the mergesort approaches, and some using `sum` or a Fenwick tree.

This program measures the execution time of each function on a series of random lists of integers; it can also verify that each function gives the same results as the others, and that it doesn't modify the input list.

Each `timeit` call gives a vector containing 3 results, which I sort. The main value to look at here is the minimum one, the other values merely give an indication of how reliable that minimum value is, as discussed in the Note in the `timeit` module docs.

Unfortunately, the output from this program is too large to include in this answer, so I'm posting it in its own (community wiki) answer.

The output is from 3 runs on my ancient 32 bit single core 2GHz machine running Python 3.6.0 on an old Debian-derivative distro. YMMV. During the tests I shut down my Web browser and disconnected from my router to minimize the impact of other tasks on the CPU.

The first run tests all the functions with list sizes from 5 to 320, with loop sizes from 4096 to 64 (as the list size doubles, the loop size is halved). The random pool used to construct each list is half the size of the list itself, so we are likely to get lots of duplicates. Some of the inversion counting algorithms are more sensitive to duplicates than others.

The second run uses larger lists: 640 to 10240, and a fixed loop size of 8. To save time it eliminates several of the slowest functions from the tests. My brute-force O(n²) functions are just way too slow at these sizes, and as mentioned earlier, my code that uses `sum`, which does so well on small to moderate lists, just can't keep up on big lists.

The final run covers list sizes from 20480 to 655360, and a fixed loop size of 4, with the 8 fastest functions. For list sizes under 40,000 or so Tim Babych's code is the clear winner. Well done Tim! Niklas B's code is a good all-round performer too, although it gets beaten on the smaller lists. The bisection-based code of "python" also does rather well, although it appears to be a little slower with huge lists with lots of duplicates, probably due to that linear `while` loop it uses to step over dupes.

However, for the very large list sizes, the bisection-based algorithms can't compete with the true O(nlogn) algorithms.

``````#!/usr/bin/env python3

''' Test speeds of various ways of counting inversions in a list

The inversion count is a measure of how sorted an array is.
A pair of items in a are inverted if i < j but a[j] > a[i]

See https://stackoverflow.com/questions/337664/counting-inversions-in-an-array

This program contains code by the following authors:
mkso
Niklas B
B. M.
Tim Babych
python
Zhe Hu
prasadvk
noman pouigt
PM 2Ring

Timing and verification code by PM 2Ring
Collated 2017.12.16
Updated 2017.12.21
'''

from timeit import Timer
from random import seed, randrange
from bisect import bisect, insort_left

seed('A random seed string')

# Merge sort version by mkso
def count_inversion_mkso(lst):
return merge_count_inversion(lst)

def merge_count_inversion(lst):
if len(lst) <= 1:
return lst, 0
middle = len(lst) // 2
left, a = merge_count_inversion(lst[:middle])
right, b = merge_count_inversion(lst[middle:])
result, c = merge_count_split_inversion(left, right)
return result, (a + b + c)

def merge_count_split_inversion(left, right):
result = []
count = 0
i, j = 0, 0
left_len = len(left)
while i < left_len and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
count += left_len - i
j += 1
result += left[i:]
result += right[j:]
return result, count

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Using a Binary Indexed Tree, aka a Fenwick tree, by Niklas B.
def count_inversions_NiklasB(a):
res = 0
counts =  * (len(a) + 1)
rank = {v: i for i, v in enumerate(sorted(a), 1)}
for x in reversed(a):
i = rank[x] - 1
while i:
res += counts[i]
i -= i & -i
i = rank[x]
while i <= len(a):
counts[i] += 1
i += i & -i
return res

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by B.M
# Modified by PM 2Ring to deal with the global counter
bm_count = 0

def merge_count_BM(seq):
global bm_count
bm_count = 0
sort_bm(seq)
return bm_count

def merge_bm(l1,l2):
global bm_count
l = []
while l1 and l2:
if l1[-1] <= l2[-1]:
l.append(l2.pop())
else:
l.append(l1.pop())
bm_count += len(l2)
l.reverse()
return l1 + l2 + l

def sort_bm(l):
t = len(l) // 2
return merge_bm(sort_bm(l[:t]), sort_bm(l[t:])) if t > 0 else l

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Bisection based method by Tim Babych
def solution_TimBabych(A):
sorted_left = []
res = 0
for i in range(1, len(A)):
insort_left(sorted_left, A[i-1])
# i is also the length of sorted_left
res += (i - bisect(sorted_left, A[i]))
return res

# Slightly faster, except for very small lists
def solutionE_TimBabych(A):
res = 0
sorted_left = []
for i, u in enumerate(A):
# i is also the length of sorted_left
res += (i - bisect(sorted_left, u))
insort_left(sorted_left, u)
return res

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Bisection based method by "python"
def solution_python(A):
B = list(A)
B.sort()
inversion_count = 0
for i in range(len(A)):
j = binarySearch_python(B, A[i])
while B[j] == B[j - 1]:
if j < 1:
break
j -= 1
inversion_count += j
B.pop(j)
return inversion_count

def binarySearch_python(alist, item):
first = 0
last = len(alist) - 1
found = False
while first <= last and not found:
midpoint = (first + last) // 2
if alist[midpoint] == item:
return midpoint
else:
if item < alist[midpoint]:
last = midpoint - 1
else:
first = midpoint + 1

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by Zhe Hu
def inv_cnt_ZheHu(a):
_, count = inv_cnt(a.copy())
return count

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)

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# Merge sort version by noman pouigt
# From https://stackoverflow.com/q/47830098
def reversePairs_nomanpouigt(nums):
def merge(left, right):
if not left or not right:
return (0, left + right)
#if everything in left is less than right
if left[len(left)-1] < right:
return (0, left + right)
else:
left_idx, right_idx, count = 0, 0, 0
merged_output = []

# check for condition before we merge it
while left_idx < len(left) and right_idx < len(right):
#if left[left_idx] > 2 * right[right_idx]:
if left[left_idx] > right[right_idx]:
count += len(left) - left_idx
right_idx += 1
else:
left_idx += 1

#merging the sorted list
left_idx, right_idx = 0, 0
while left_idx < len(left) and right_idx < len(right):
if left[left_idx] > right[right_idx]:
merged_output += [right[right_idx]]
right_idx += 1
else:
merged_output += [left[left_idx]]
left_idx += 1
if left_idx == len(left):
merged_output += right[right_idx:]
else:
merged_output += left[left_idx:]
return (count, merged_output)

def partition(nums):
count = 0
if len(nums) == 1 or not nums:
return (0, nums)
pivot = len(nums)//2
left_count, l = partition(nums[:pivot])
right_count, r = partition(nums[pivot:])
temp_count, temp_list = merge(l, r)
return (temp_count + left_count + right_count, temp_list)
return partition(nums)

# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# PM 2Ring
def merge_PM2R(seq):
seq, count = merge_sort_count_PM2R(seq)
return count

def merge_sort_count_PM2R(seq):
mid = len(seq) // 2
if mid == 0:
return seq, 0
left, left_total = merge_sort_count_PM2R(seq[:mid])
right, right_total = merge_sort_count_PM2R(seq[mid:])
total = left_total + right_total
result = []
i = j = 0
left_len, right_len = len(left), len(right)
while i < left_len and j < right_len:
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
total += left_len - i
result.extend(left[i:])
result.extend(right[j:])
return result, total

def rank_sum_PM2R(a):
total = 0
counts =  * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += sum(counts[:i])
counts[i] += 1
return total

# Fenwick tree functions adapted from C code on Wikipedia
def fen_sum(tree, i):
''' Return the sum of the first i elements, 0 through i-1 '''
total = 0
while i:
total += tree[i-1]
i -= i & -i
return total

def fen_add(tree, delta, i):
''' Add delta to element i and thus
to fen_sum(tree, j) for all j > i
'''
size = len(tree)
while i < size:
tree[i] += delta
i += (i+1) & -(i+1)

def fenwick_PM2R(a):
total = 0
counts =  * len(a)
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
total += fen_sum(counts, i)
fen_add(counts, 1, i)
return total

def fenwick_inline_PM2R(a):
total = 0
size = len(a)
counts =  * size
rank = {v: i for i, v in enumerate(sorted(a))}
for u in reversed(a):
i = rank[u]
j = i + 1
while i:
total += counts[i]
i -= i & -i
while j < size:
counts[j] += 1
j += j & -j
return total

def bruteforce_loops_PM2R(a):
total = 0
for i in range(1, len(a)):
u = a[i]
for j in range(i):
if a[j] > u:
total += 1
return total

def bruteforce_sum_PM2R(a):
return sum(1 for i in range(1, len(a)) for j in range(i) if a[j] > a[i])

# Using binary tree counting, derived from C++ code (?) by prasadvk
# https://stackoverflow.com/a/16056139
def ltree_count_PM2R(a):
total, root = 0, None
for u in a:
# Store data in a list-based tree structure
# [data, count, left_child, right_child]
p = [u, 0, None, None]
if root is None:
root = p
continue
q = root
while True:
if p < q:
total += 1 + q
child = 2
else:
q += 1
child = 3
if q[child]:
q = q[child]
else:
q[child] = p
break
return total

# Counting based on radix sort, recursive version
def radix_partition_rec(a, L):
if len(a) < 2:
return 0
if len(a) == 2:
return a < a
left, right = [], []
count = 0
for u in a:
if u & L:
right.append(u)
else:
count += len(right)
left.append(u)
L >>= 1
if L:
count += radix_partition_rec(left, L) + radix_partition_rec(right, L)
return count

# The following functions determine swaps using a permutation of
# range(len(a)) that has the same inversion count as `a`. We can create
# this permutation with `sorted(range(len(a)), key=lambda k: a[k])`
# but `sorted(range(len(a)), key=a.__getitem__)` is a little faster.

# Counting based on radix sort, iterative version
def radix_partition_iter(seq, L):
count = 0
parts = [seq]
while L and parts:
newparts = []
for a in parts:
if len(a) < 2:
continue
if len(a) == 2:
count += a < a
continue
left, right = [], []
for u in a:
if u & L:
right.append(u)
else:
count += len(right)
left.append(u)
if left:
newparts.append(left)
if right:
newparts.append(right)
parts = newparts
L >>= 1
return count

def perm_radixR_PM2R(a):
size = len(a)
b = sorted(range(size), key=a.__getitem__)
n = size.bit_length() - 1
return radix_partition_rec(b, 1 << n)

def perm_radixI_PM2R(a):
size = len(a)
b = sorted(range(size), key=a.__getitem__)
n = size.bit_length() - 1
return radix_partition_iter(b, 1 << n)

# Plain sum of the counts of the permutation
def perm_sum_PM2R(a):
total = 0
size = len(a)
counts =  * size
for i in reversed(sorted(range(size), key=a.__getitem__)):
total += sum(counts[:i])
counts[i] = 1
return total

# Fenwick sum of the counts of the permutation
def perm_fenwick_PM2R(a):
total = 0
size = len(a)
counts =  * size
for i in reversed(sorted(range(size), key=a.__getitem__)):
j = i + 1
while i:
total += counts[i]
i -= i & -i
while j < size:
counts[j] += 1
j += j & -j
return total

# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# All the inversion-counting functions
funcs = (
solution_TimBabych,
solutionE_TimBabych,
solution_python,
count_inversion_mkso,
count_inversions_NiklasB,
merge_count_BM,
inv_cnt_ZheHu,
reversePairs_nomanpouigt,
fenwick_PM2R,
fenwick_inline_PM2R,
merge_PM2R,
rank_sum_PM2R,
bruteforce_loops_PM2R,
bruteforce_sum_PM2R,
ltree_count_PM2R,
perm_radixR_PM2R,
perm_radixI_PM2R,
perm_sum_PM2R,
perm_fenwick_PM2R,
)

def time_test(seq, loops, verify=False):
orig = seq
timings = []
for func in funcs:
seq = orig.copy()
value = func(seq) if verify else None
t = Timer(lambda: func(seq))
result = sorted(t.repeat(3, loops))
timings.append((result, func.__name__, value))
assert seq==orig, 'Sequence altered by {}!'.format(func.__name__)
first = timings[-1]
timings.sort()
for result, name, value in timings:
result = ', '.join([format(u, '.5f') for u in result])
print('{:24} : {}'.format(name, result))

if verify:
# Check that all results are identical
bad = ['%s: %d' % (name, value)
for _, name, value in timings if value != first]
if bad:
print('ERROR. Value: {}, bad: {}'.format(first, ', '.join(bad)))
else:
print('Value: {}'.format(first))
print()

#Run the tests
size, loops = 5, 1 << 12
verify = True
for _ in range(7):
hi = size // 2
print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
seq = [randrange(hi) for _ in range(size)]
time_test(seq, loops, verify)
loops >>= 1
size <<= 1

#size, loops = 640, 8
#verify = False
#for _ in range(5):
#hi = size // 2
#print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
#seq = [randrange(hi) for _ in range(size)]
#time_test(seq, loops, verify)
#size <<= 1

#size, loops = 163840, 4
#verify = False
#for _ in range(3):
#hi = size // 2
#print('Size = {}, hi = {}, {} loops'.format(size, hi, loops))
#seq = [randrange(hi) for _ in range(size)]
#time_test(seq, loops, verify)
#size <<= 1
``````

Please see here for the output

2017/12/21

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Email: [email protected]