I'm trying to count the numer of inversions in a list. A predicate inversion(+L,-N) unifies N to the number of inversions in that list. A inversion is defined as X > Y and X appears before Y in the list (unless X or Y is 0). For example:
?- inversions([1,2,3,4,0,5,6,7,8],N).
N = 0.
?- inversions([1,2,3,0,4,6,8,5,7],N).
N = 3.
For what I'm using this for, the list will always have exacly 9 elements, and always containing the numbers 0-8 uniquely.
I'm quite new to Prolog and I'm trying to do this as concise and as elegant as possible; It seems like DCG will probably help a lot. I read into the official definition and some tutorial sites, but still don't quit understand what it is. Any help would be greatly appreciated.
Such application-specific constraints can often be built using reified constraints (constraints whose truth value is reflected into a 0/1 variable). This leads to a relatively natural formulation, where B is 1 iff the condition you want to count is satisfied:
:- lib(ic).
inversions(Xs, N) :-
( fromto(Xs, [X|Ys], Ys, [_]), foreach(NX,NXs) do
( foreach(Y,Ys), param(X), foreach(B,Bs) do
B #= (X#\=0 and Y#\=0 and X#>Y)
),
NX #= sum(Bs) % number of Ys that are smaller than X
),
N #= sum(NXs).
This code is for ECLiPSe.