DCG和Prolog中列表的反转

Question

我试图在列表中计算反转的数量.谓词inversion(+L,-N)统一N了该列表中的反转次数.甲反转被定义为X > Y与X之前出现Y在列表中(除非X或Y是0).例如:

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

对于我正在使用的内容,列表将始终包含9个元素,并且始终包含0-8唯一的数字.

我对Prolog很新,我试图尽可能简洁,优雅; 似乎DCG可能会有很大帮助.我读了官方定义和一些教程网站,但仍然没有放弃了解它是什么.任何帮助将不胜感激.

Answer 1

这是另一个不使用选择点的解决方案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
   ).

Answer 2

这种特定于应用程序的约束通常可以使用具体化约束（其真值反映为 0/1 变量的约束）来构建。这导致了一个相对自然的公式，其中 B 为 1，当且仅当满足您要计数的条件：

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

此代码适用于ECLiPSe。