我不确定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_inv([], 0).
count_inv([X|T], C) :-
count_inv(X, T, C1),
C #= C1 + C2,
count_inv(T, C2).
count_inv(_, [], 0).
count_inv(X, [Y|T], C) :-
( X #> Y, X #> 0, Y #> 0
-> C #= C1 + 1,
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) :-
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, 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([], 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).
你可以忽略第二个参数,它是已排序的列表(如果你只想要逆序对的数量,这只是一个副作用)。
X
在列表中出现在Y
之前…” 这是指“立即”之后,还是在任何时间点之后? - lurker