# Counting number of inversions

Is there an inbuilt method to find the number of inversions in a set of numbers? I found Inversions in Combinatorica but when I tried to use it as Inversions[{1,4,2,5,2,3,2}] it doesn't return a number as a result. How are you supposed to use the function?

-
That's because {1,4,2,5,2,3,2} is not a permutation. A permutation of length n contains precisely the elements Range[n] in some order. –  Szabolcs Jun 6 '14 at 17:35
Also, to use a function in Combinatorica you must first load the package with Needs["Combinatorica"] –  Bob Hanlon Jun 6 '14 at 17:46
@Szabolcs Is there any way to make it work for a general set of elements? –  1110101001 Jun 6 '14 at 18:16
@user2612743 You'll have to roll your own. The simplest approach is brute forcing it as george2079 did. –  Szabolcs Jun 6 '14 at 19:35

## 3 Answers

Something like this?

 myinversions[list_] :=
Select[ Subsets[Range[Length[list]], {2}] ,
list[[#[[1]]]] > list[[#[[2]]]] & ] // Length


Verify the same result as builtin Inversions for a permutation

 Needs["Combinatorica"]
And @@ (Inversions[#] == myinversions[#] & /@ Permutations[Range[5]])


True

 myinversions[{1, 4, 2, 5, 2, 3, 2}]


8

-

Update: Still 4X slower than @Mr.W' method, but much faster than ones in the original post is

 invF5 = With[{ss = Subtract @@ Transpose[Subsets[#, {2}]]}, Total@UnitStep[ss]] &


invF = Total@(1 - UnitStep[Order @@@ Subsets[#, {2}]]) &


or

invF2 = Count[Subsets[#, {2}], _?(Greater @@ # &)] &;


or, variations on george2079's approach

invF3 = Length@Select[Subsets[#, {2}], Greater @@ # &] &;
invF4 = Length@Select[Subsets[#, {2}], Composition[Not, OrderedQ]] &;

l1 = RandomSample[Range[5]];
{l1, invF[l1], invF2[l1], invF3[l1], invF4[l1]}
(* {{5,4,1,3,2}, 8, 8, 8, 8} *)


Using the test in @george2079's answer:

And @@ Equal @@@ ({invF[#], invF2[#], invF3[#], invF4[#], myinversions[#]} & /@
Permutations[Range[5]])
(* True *)

-

The presently Accepted solution is quite slow, at least on long lists. We can improve performance of this brute-force algorithm by orders of magnitude using numeric vector operations. Consider:

f1[a_] /; VectorQ[a, IntegerQ] :=
Sum[Tr @ Clip[a[[i]] ~Subtract~ Drop[a, i], {0, 1}], {i, Length@a}]

f1[a_List] := f1 @ Ordering @ a


Compared to myinversions on numeric data:

big = RandomInteger[5000, 2000];
r1 = myinversions[big]; // Timing // First
r2 = f1[big]; // Timing // First
r1 === r2

2.589
0.01684
True


The second definition lets the function operate on arbitrary expressions by converting with Ordering:

RandomChoice[DictionaryLookup[], 6]
% // f1

{"illustrate", "reconstruct", "fine", "furry", "Ivorian", "dinghy"}
10


I suspect there is a yet faster way using a sort-based algorithm.

-
If you want the fastest O(n*lg(n)) version you could use mergesort and piggyback on the merging method to count the inversions and use the recursive sort to add them all up. –  1110101001 Jun 7 '14 at 16:23
As an alternative, use binary indexed trees to store the frequencies and count number of times a number greater than the current number occurs. I'm not sure how to code either of these in mathematica though. –  1110101001 Jun 7 '14 at 16:24