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.

*...and `X` appears before `Y` in the list...* Is that *immediately* after, or at any point after? — lurker, May 10 '17 at 10:51
This is really a nice clpfd-example. I will put a bounty for a clpfd-solution — false, May 10 '17 at 11:23

score 5 · Answer 1 · edited May 13 '17 at 20:47

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
   ).

lurker · Answer 2 · 2017-05-13T23:52:20.187

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).

Looks like many open CPs. Also `((L #> 0, R #> 0) ->` ... looks highly suspicious! — false, May 13 '17 at 17:37
@false indeed, it exhibits CPs. It is a naive approach. I did update the `->` expression since it was a little excessive. — lurker, May 13 '17 at 23:09
@false good suggestion. I wasn't very familiar with the `#<==>/2` operator. — lurker, May 13 '17 at 23:51

score 4 · Answer 3 · edited May 23 '17 at 11:47

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.

joel76 · Answer 4 · 2017-05-14T21:23:58.900

3

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.

edited May 14 '17 at 21:23

answered May 10 '17 at 17:24

joel76

5,565
1
18
22

@false : tu es français ? – joel76 May 14 '17 at 21:25
1

Rendons grâce à Alain Colmerauer ! – joel76 May 15 '17 at 15:27
C'est seulment maintenant que j'ai appris [la triste nouvelle](https://twitter.com/fbenhamou/status/864088974205349888)! – false May 16 '17 at 20:23
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. – joel76 May 16 '17 at 22:14

score 3 · Accepted Answer · answered May 11 '17 at 00:00

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.

`inversions(Xs, 1).` fails, yet `Xs = [2,1,0], inversions(Xs, 1).` succeeds using 6.2development #21. Is there a better version? — false, May 13 '17 at 17:33

CapelliC · Answer 6 · 2017-05-14T21:54:47.483

2

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.

edited May 14 '17 at 21:54

answered May 10 '17 at 06:32

CapelliC

59,646
5
47
90

1

While `inversions([0,2,1],1).` succeeds its generalization `inversions([0,2,X],1).` fails. – false May 10 '17 at 11:20
Why don't you fix your program? It's so easy like replacing `\=` by `=\=` or putting `X>Y` first! – false May 13 '17 at 23:42
@false: thanks, I'll do... I had a short attempt to using clpfd:element/3, but it didn't worked – CapelliC May 14 '17 at 05:43
2

aggregate and clpfd do not flock together: `inversions([0,1,2],N).` now fails?? – false May 14 '17 at 20:22
1

Also, please use a separate answer for a separate solution. – false May 14 '17 at 20:24
Now, `inversions([0,2,1],0)` succeeds and at the same time `inversions([0,2,1],1)` succeeds. – false May 17 '17 at 17:45

DCG and inversion of a list in Prolog

6 Answers6