list - 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

这种特定于应用程序的约束通常可以使用具体化约束(其真值反射(reflect)到 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 .