一个用于置换奇偶校验的Prolog程序

Question

我用Prolog写了这个小程序。

odd_even_flip(odd, even).
odd_even_flip(even, odd).
% flip_one, for A = a, B = b, P = [a, .., b, ..], gives M = [b, .., a, ..]
flip_one(A, B, P, M) :-
append([A|As], [B|Bs], P),
append([B], As, L),
append([A], Bs, R),
append(L, R, M).

permutation_parity([X|L], [X|P], R) :- permutation_parity(L, P, R).
% abc
permutation_parity([X|L], [Y|P], R) :-
X = Y,
flip_one(Y, X, [Y|P], M),
permutation_parity([X|L], M, Res),
odd_even_flip(Res, R).
permutation_parity([], [], even).

我期望它能找到列表l的一个排列p的奇偶性。少数断言给定列表的一个给定排列确实是偶数或奇数的查询工作得很好。

然而，根据我使用Prolog的经验，我希望permutation_parity([a, b, c]， X, Y).会显示出[a, b, c]的所有排列，但这并没有发生。

我得到X = [a, b, c]， Y = even。

我试图在%abc后面的规则中添加成员(Y, L)，因为我认为这将有助于Prolog知道如何在permutation_parity([a, b, c]， X, Y)中实例化X，但这无济于事。

如果有人能帮我看看我错过了什么，那就太好了。提前谢谢。

Answer 1

您只需要使用统一来正确地实例化变量X(假设调用permutation_parity/3时使用适当的列表作为其第一个参数)。所以我建议你修改你的代码如下:

permutation_parity([], [], even).
permutation_parity([X|Xs], [X|Zs], P) :-
permutation_parity(Xs, Zs, P).
permutation_parity([X|Xs], Zs, P) :-
permutation_parity(Xs, Ys, Q),
flip_first([X|Ys], Zs),
odd_even_flip(Q, P).
flip_first(L0, L1) :-
append([X|Xs], [Y|Ys], L0),
append([Y|Xs], [X|Ys], L1).
odd_even_flip(odd, even).
odd_even_flip(even, odd).

例子:

?- permutation_parity([a,b,c], Permutation, Parity).
Permutation = [c, a, b],
Parity = even ;
Permutation = [b, c, a],
Parity = even ;
Permutation = [b, a, c],
Parity = odd ;
Permutation = [c, b, a],
Parity = odd ;
Permutation = [a, c, b],
Parity = odd ;
Permutation = [a, b, c],
Parity = even.
?- permutation_parity([a,b,c], [a,c,b], Parity).
Parity = odd ;
false.
?- permutation_parity([a,b,c], Permutation, even).
Permutation = [c, a, b] ;
Permutation = [b, c, a] ;
Permutation = [a, b, c].

编辑

perm_parity(L0, L1, P) :-
same_length(L0, L1),
permutation_parity(L0, L1, P).

谓词same_length/2在wi - prolog中定义如下:

same_length([], []).
same_length([_|T1], [_|T2]) :-
same_length(T1, T2).

的例子:

?- perm_parity(L, [a,b,c], P).
L = [b, c, a],
P = even ;
L = [c, a, b],
P = even ;
L = [b, a, c],
P = odd ;
L = [c, b, a],
P = odd ;
L = [a, c, b],
P = odd ;
L = [a, b, c],
P = even.