5
$\begingroup$

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?

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

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

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

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 *)
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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