DCG and inversion of a list in Prolog

Question

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.

Southbound

...and X appears before Y in the list... Is that immediately after, or at any point after? – Frug

This is really a nice clpfd-example. I will put a bounty for a clpfd-solution – Siouxie

@lurker, any point before – Southbound

Answer 1

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.

Oxfordshire

inversions(Xs, 1). fails, yet Xs = [2,1,0], inversions(Xs, 1). succeeds using 6.2development #21. Is there a better version? – Siouxie

Answer 2

Here is another solution that doesn't leave choice points using if_/3:

inversions([],0).
inversions([H|T], N):-
   if_( H = 0, 
        inversions(T,N),
        ( find_inv(T,H,N1),inversions(T, N2), N #= N1+N2 )
      ).

find_inv([],_,0).
find_inv([H1|T],H,N1):-
   if_( H1=0,
        find_inv(T,H,N1),
        if_( H#>H1, 
             (find_inv(T,H,N2),N1 #= N2+1),
             find_inv(T,H,N1) 
           )
       ).

#>(X, Y, T) :-
   (  integer(X),
      integer(Y)
   -> ( X > Y
      -> T = true
      ;  T = false
      )
   ;  X #> Y,
      T = true
   ;  X #=< Y,
      T = false
   ).

Charo

Answer 3

I'm not so sure a DCG would be helpful here. Although we're processing a sequence, there's a lot of examination of the entire list at each point when looking at each element.

Here's a CLPFD approach which implements the "naive" algorithm for inversions, so it's transparent and simple, but not as efficient as it could be (it's O(n^2)). There's a more efficient algorithm (O(n log n)) involving a divide and conquer approach, which I show further below.

:- use_module(library(clpfd)).

inversions(L, C) :-
    L ins 0..9,
    all_distinct(L),
    count_inv(L, C).

% Count inversions    
count_inv([], 0).
count_inv([X|T], C) :-
    count_inv(X, T, C1),     % Count inversions for current element
    C #= C1 + C2,            % Add inversion count for the rest of the list
    count_inv(T, C2).        % Count inversions for the rest of the list

count_inv(_, [], 0).
count_inv(X, [Y|T], C) :-
    (   X #> Y, X #> 0, Y #> 0
    ->  C #= C1 + 1,         % Valid inversion, count it
        count_inv(X, T, C1)
    ;   count_inv(X, T, C)
    ).

?- inversions([1,2,3,4,0,5,6,7,8],N).
N = 0 ;
false.

?- inversions([1,2,3,0,4,6,8,5,7],N).
N = 3 ;
false.

?-  inversions([0,2,X],1).
X = 1 ;
false.

It does leave a choice point, as you can see, which I haven't sorted out yet.

---

Here's the O(n log n) solution, which is using the sort/merge algorithm.

inversion([], [], 0).
inversion([X], [X], 0).
inversion([HU1, HU2|U], [HS1, HS2|S], C) :- % Ensure list args have at least 2 elements
    split([HU1, HU2|U], L, R),
    inversion(L, SL, C1),
    inversion(R, SR, C2),
    merge(SL, SR, [HS1, HS2|S], C3),
    C #= C1 + C2 + C3.

% Split list into left and right halves
split(List, Left, Right) :-
    split(List, List, Left, Right).
split(Es, [], [], Es).
split(Es, [_], [], Es).
split([E|Es], [_,_|T], [E|Ls], Right) :-
    split(Es, T, Ls, Right).

% merge( LS, RS, M )
merge([], RS, RS, 0).
merge(LS, [], LS, 0).
merge([L|LS], [R|RS], [L|T], C) :-
    L #=< R,
    merge(LS, [R|RS], T, C).
merge([L|LS], [R|RS], [R|T], C) :-
    L #> R, R #> 0 #<==> D, C #= C1+D,
    merge([L|LS], RS, T, C1).

You can ignore the second argument, which is the sorted list (just a side effect if all you want is the count of inversions).

Frug

Looks like many open CPs. Also ((L #> 0, R #> 0) -> ... looks highly suspicious! – Siouxie

@Siouxie indeed, it exhibits CPs. It is a naive approach. I did update the -> expression since it was a little excessive. – Frug

@Siouxie good suggestion. I wasn't very familiar with the #<==>/2 operator. – Frug

Answer 4

Here is another possibility to define the relation. First, #</3 and #\=/3 can be defined like so:

:- use_module(library(clpfd)).

bool_t(1,true).
bool_t(0,false).

#<(X,Y,Truth)  :- X #< Y #<==> B, bool_t(B,Truth).
#\=(X,Y,Truth)  :- X #\= Y #<==> B, bool_t(B,Truth).

Based on that, if_/3 and (',')/3 a predicate inv_t/3 can be defined, that yields true in the case of an inversion and false otherwise, according to the definition given by the OP:

inv_t(X,Y,T) :-
   if_(((Y#<X,Y#\=0),X#\=0),T=true,T=false).

And subsequently the actual relation can be described like so:

list_inversions(L,I) :-
   list_inversions_(L,I,0).

list_inversions_([],I,I).
list_inversions_([X|Xs],I,Acc0) :-
   list_x_invs_(Xs,X,I0,0),
   Acc1 #= Acc0+I0,
   list_inversions_(Xs,I,Acc1).

list_x_invs_([],_X,I,I).
list_x_invs_([Y|Ys],X,I,Acc0) :-
   if_(inv_t(X,Y),Acc1#=Acc0+1,Acc1#=Acc0),
   list_x_invs_(Ys,X,I,Acc1).

Thus the example queries given by the OP succeed deterministically:

?- list_inversions([1,2,3,4,0,5,6,7,8],N).
N = 0.

?- list_inversions([1,2,3,0,4,6,8,5,7],N).
N = 3.

Morpho

Answer 5

Using clpfd et automaton/8 we can write

:- use_module(library(clpfd)).

inversions(Vs, N) :-
             Vs ins 0..sup,
             variables_signature(Vs, Sigs),
             automaton(Sigs, _, Sigs,
                       [source(s),sink(i),sink(s)],
                       [arc(s,0,s), arc(s,1,s,[C+1]), arc(s,1,i,[C+1]),
                        arc(i,0,i)],
                       [C], [0], [N]),
            labeling([ff],Vs).

variables_signature([], []).

variables_signature([V|Vs], Sigs) :-
            variables_signature_(Vs, V, Sigs1),
            variables_signature(Vs, Sigs2),
            append(Sigs1, Sigs2, Sigs).

variables_signature_([], _, []).

variables_signature_([0|Vs], Prev, Sigs) :-
      variables_signature_(Vs,Prev,Sigs).

variables_signature_([V|Vs], Prev, [S|Sigs]) :-
      V #\= 0,
      % Prev #=< V #<==> S #= 0,
      % modified after **false** remark 
      Prev #> V #<==> S,
      variables_signature_(Vs,Prev,Sigs).

examples :

?- inversions([1,2,3,0,4,6,8,5,7],N).
N = 3 ;
false.

?- inversions([1,2,3,0,4,5,6,7,8],N).
N = 0 ;
false.

?- inversions([0,2,X],1).
X = 1.

Cozen

@Siouxie : tu es français ? – Cozen

Rendons grâce à Alain Colmerauer ! – Cozen

C'est seulment maintenant que j'ai appris la triste nouvelle! – Siouxie

Ouch ! Je dois dire que je ne savais rien de ce décès : je plaisantais sur le fait que gràce à Alain Colmerauer, tu avais appris le français pour étudier son Prolog dans sa langue. – Cozen

Answer 6

in SWI-Prolog, with libraries aggregate and lists:

inversions(L,N) :-
    aggregate_all(count, (nth1(P,L,X),nth1(Q,L,Y),X\=0,Y\=0,X>Y,P<Q), N).

both libraries are autoloaded, no need to explicitly include them.

If you want something more general, you can see the example in library(clpfd), under the automaton section, for some useful ideas. But I would try to rewrite your specification in simpler terms, using element/3 instead of nth1/3.

edit

after @false comment, I tried some variation on disequality operators, but none I've tried have been able to solve the problematic query. Then I tried again with the original idea, to put to good use element/3. Here is the result:

:- use_module(library(clpfd)).

inversions(L) :-
    L ins 0..8,
    element(P,L,X),
    element(Q,L,Y),
    X #\= 0, Y #\= 0, X #> Y, P #< Q,
    label([P,Q]).

inversions(L,N) :-
    aggregate(count, inversions(L), N) ; N = 0.

The last line label([P,Q]) it's key to proper reification: now we can determine the X value.

?- inversions([0,2,X],1).
X = 1.

Disproportion

While inversions([0,2,1],1). succeeds its generalization inversions([0,2,X],1). fails. – Siouxie

Why don't you fix your program? It's so easy like replacing \= by =\= or putting X>Y first! – Siouxie

@false: thanks, I'll do... I had a short attempt to using clpfd:element/3, but it didn't worked – Disproportion

aggregate and clpfd do not flock together: inversions([0,1,2],N). now fails?? – Siouxie

Also, please use a separate answer for a separate solution. – Siouxie

Now, inversions([0,2,1],0) succeeds and at the same time inversions([0,2,1],1) succeeds. – Siouxie