Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
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
up vote 3 down vote accepted

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

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


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


share|improve this answer

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}]]) &


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[#]} & /@ 
(* True *)
share|improve this answer

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

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

RandomChoice[DictionaryLookup[], 6]
% // f1
{"illustrate", "reconstruct", "fine", "furry", "Ivorian", "dinghy"}

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

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.