Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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
2  
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 at 17:35
    
Also, to use a function in Combinatorica you must first load the package with Needs["Combinatorica`"] –  Bob Hanlon Jun 6 at 17:46
    
@Szabolcs Is there any way to make it work for a general set of elements? –  user2612743 Jun 6 at 18:16
    
@user2612743 You'll have to roll your own. The simplest approach is brute forcing it as george2079 did. –  Szabolcs Jun 6 at 19:35

3 Answers 3

up vote 4 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

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

True

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

8

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

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 *)
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
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.

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. –  user2612743 Jun 7 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. –  user2612743 Jun 7 at 16:24

Your Answer

 
discard

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.