DCG 和 Prolog 中列表的反转
DCG and inversion of a list in Prolog
我正在计算列表中 反转 的数量。谓词 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 可能会有很大帮助。我阅读了官方定义和一些教程网站，但仍然不明白它是什么。任何帮助将不胜感激。
在 SWI-Prolog 中，带有库 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).
两个库都是自动加载的，无需明确包含它们。
如果你想要更通用的东西，你可以在库中查看示例（clpfd), under the automaton section, for some useful ideas. But I would try to rewrite your specification in simpler terms, using element/3 而不是 nth1/3。
编辑
在@false 发表评论后，我尝试了一些不等式运算符的变体，但是 none 我已经尝试过能够解决有问题的查询。然后我又按照原来的想法再试了一次，好好利用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.
我不太确定 DCG 在这里会有帮助。虽然我们正在处理一个序列，但在查看每个元素时，在每个点都会对整个列表进行大量检查。
这是一个 CLPFD 方法，它实现了 "naive" 算法进行反演，因此它是透明和简单的，但效率不高（它是 O(n ^2)).有一种更有效的算法 (O(n log n)) 涉及 divide and conquer 方法，我将在下面进一步展示。
:- 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) 解决方案，它使用 sort/merge 算法。
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).
您可以忽略第二个参数，它是已排序的列表（如果您只需要反转的计数，这只是一个副作用）。
使用 clpfd et 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.
此类特定于应用程序的约束通常可以使用具体化约束（真值反映到 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。
这是另一个不留下选择点的解决方案 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
).
这是定义关系的另一种可能性。首先，#</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).
基于此，if_/3 and 可以定义谓词 inv_t/3，根据 OP 给出的定义，在反转的情况下产生 true，否则产生 false：
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.
我正在计算列表中 反转 的数量。谓词 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 可能会有很大帮助。我阅读了官方定义和一些教程网站，但仍然不明白它是什么。任何帮助将不胜感激。
在 SWI-Prolog 中，带有库 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).
两个库都是自动加载的，无需明确包含它们。
如果你想要更通用的东西，你可以在库中查看示例（clpfd), under the automaton section, for some useful ideas. But I would try to rewrite your specification in simpler terms, using element/3 而不是 nth1/3。
编辑
在@false 发表评论后，我尝试了一些不等式运算符的变体，但是 none 我已经尝试过能够解决有问题的查询。然后我又按照原来的想法再试了一次，好好利用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.
我不太确定 DCG 在这里会有帮助。虽然我们正在处理一个序列，但在查看每个元素时，在每个点都会对整个列表进行大量检查。
这是一个 CLPFD 方法，它实现了 "naive" 算法进行反演，因此它是透明和简单的，但效率不高（它是 O(n ^2)).有一种更有效的算法 (O(n log n)) 涉及 divide and conquer 方法，我将在下面进一步展示。
:- 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) 解决方案，它使用 sort/merge 算法。
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).
您可以忽略第二个参数，它是已排序的列表（如果您只需要反转的计数，这只是一个副作用）。
使用 clpfd et 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.
此类特定于应用程序的约束通常可以使用具体化约束（真值反映到 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。
这是另一个不留下选择点的解决方案 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
).
这是定义关系的另一种可能性。首先，#</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).
基于此，if_/3 and inv_t/3，根据 OP 给出的定义，在反转的情况下产生 true，否则产生 false：
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.