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会非常有帮助。我已经阅读了官方定义和一些教程网站，但仍然不太理解它是什么。任何帮助都将不胜感激。

- bli00

---

“...并且X在列表中出现在Y之前…” 这是指“立即”之后，还是在任何时间点之后？ - lurker

这确实是一个不错的clpfd示例。我会为clpfd解决方案设置赏金。 - false

@lurker，在任何一点之前。 - bli00

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

- coder

Answer 2

我不确定DCG在这里是否有帮助。虽然我们正在处理一个序列，但在查看每个元素时，在每个点上对整个列表进行了大量的检查。

这里是一个CLPFD方法，它实现了反转的“天真”算法，因此它是透明且简单的，但效率不如它本应该的（它是O(n^2)）。还有一种更有效的算法（O(n log n)），涉及到分治方法，我将在下面进一步展示。

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

我还没有解决它留下的选择点，正如您所看到的。

---

这是O(n log n)解决方案，使用排序/合并算法。

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

你可以忽略第二个参数，它是已排序的列表（如果你只想要逆序对的数量，这只是一个副作用）。

- lurker

---

看起来有许多开放的CP。另外((L #> 0, R #> 0) ->...看起来非常可疑！ - false

@false确实展示了CPs。这是一种天真的方法。我更新了->表达式，因为它有点过度。 - lurker

@false 是一个很好的建议。我对 #<==>/2 运算符并不是很熟悉。 - lurker

Answer 3

这里有另一种定义关系的可能性。首先，#</3 和 #\=/3 可以这样定义：

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

基于此，可以定义谓词inv_t/3，它使用if_/3 和 (',')/3，根据提问者给出的定义，在反演的情况下返回真，否则返回假。

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

随后，实际关系可以描述如下：

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

因此，由OP提供的示例查询可以确定地成功执行。

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

- tas

Answer 4

使用clpfd和automaton/8，我们可以编写以下代码：

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

示例：

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

- joel76

---

@false：你是法国人吗？ - joel76

让我们感谢Alain Colmerauer！ - joel76

现在我才得知这个悲伤的消息! - false

哎呀！我必须说，我对这个死讯一无所知：我只是开玩笑说，由于Alain Colmerauer的缘故，你学会了法语以便用他的Prolog语言进行研究。 - joel76

Answer 5

这样的应用程序特定限制通常可以使用具体化的约束条件（将真值反映为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 设计的。

- jschimpf

---

inversions(Xs, 1). 失败了，但是 Xs = [2,1,0], inversions(Xs, 1). 在6.2development #21中成功了。是否有更好的版本？ - false

Answer 6

在SWI-Prolog中，使用库aggregate和lists：

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

两个库都是自动加载的，无需显式包含它们。

如果你想要更一般化的东西，你可以参考library(clpfd)中的示例，在自动机部分中，获取一些有用的思路。但我建议您尝试使用element/3来简化您的规范，而不是nth1/3。

编辑

在@false的评论之后，我尝试了一些不等运算符的变化，但我尝试过的任何一种方法都无法解决问题查询。然后我再次尝试使用原始想法，充分利用element/3。以下是结果：

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

最后一行 label([P,Q]) 是正确实现具体化的关键：现在我们可以确定 X 的值。

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

- CapelliC

---

当 inversions([0,2,1],1). 成功时，它的概括 inversions([0,2,X],1). 失败。 - false

为什么不修复你的程序呢？这很容易，只需要将\=替换为=\=或者将X>Y放在第一位即可！ - false

@false：谢谢，我会尝试的...我曾经尝试使用clpfd:element/3，但它没有起作用。 - CapelliC

聚合和 CLPFD 不兼容： inversions([0,1,2],N) 现在失败了吗？ - false

另外，请为不同的解决方案使用单独的答案。 - false

现在，inversions([0,2,1],0) 成功了，同时 inversions([0,2,1],1) 也成功了。 - false