DCG and inversion of a list in Prolog
clpfd, list, prolog
Solution
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.
Problem
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.