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?
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
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.
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 *)
{1,4,2,5,2,3,2}
is not a permutation. A permutation of lengthn
contains precisely the elementsRange[n]
in some order. $\endgroup$ – Szabolcs Jun 6 '14 at 17:35Combinatorica
you must first load the package with Needs["Combinatorica`"] $\endgroup$ – Bob Hanlon Jun 6 '14 at 17:46