Prolog:使用递归在多个列表上成对兼容

Question

所以我有一个谓词:

compatible([],_).
compatible(_,[]).
compatible([HA|TA],[HB|TB]) :-
    HA \= HB,
    compatible(TA,TB).

它目前需要两个列表并确定它们是否成对兼容,如果是,则返回true,否则返回false.

例如:

?- compatible([8,2,6,3,67],[7,4,7,4,3]).
true 

?- compatible([8,2,6,3,3],[7,4,7,4,3]).
false.

第二次调用返回false,因为3位于两个列表的第5位.

我的问题是我如何修改这个谓词,以便递归检查2个以上的列表.潜在地,谓词可以检查包含1,2,3,4,5或甚至无限列表的列表列表.如果任何列表彼此不兼容,它将返回false.

因此,我可以检查3个列表,如下所示:

let Y = [[8,2,6,3,67],[7,4,7,4,3],[1,3,42,1,52]]
then...

?- compatible(Y).
true 

let Z = [[8,2,6,3,67],[7,4,7,4,3],[1,3,6,1,52]]
then...

?- compatible(Z).
false.

第二次调用失败的原因是6位于列表1和3的第3位.

Answer 1

如果所有子列表的长度相同,并且元素总是整数,则可以根据库提供的两个谓词来定义问题(clpfd):

compatible(Ls) :-
    transpose(Ls, T),
    maplist(all_different, T).

通过这个定义,您的示例:

?- compatible([[8,2,6,3,67],[7,4,7,4,3],[1,3,42,1,52]]).
true.

?- compatible([[8,2,6,3,67],[7,4,7,4,3],[1,3,6,1,52]]).
false.

如果子列表可以具有不同的长度,则应首先找到最短的,并将其余部分切割为该长度.

如果列表的元素可以是任意的Prolog术语,请看一下这个问题.简而言之:

all_different_terms([]).
all_different_terms([H|T]) :-
    maplist(dif(H), T),
    all_different_terms(T).

注意使用dif/2而不是\=/2.

?- compatible_terms([[a,b,c],[d,e,f],[g,h,i]]).
true.

?- compatible_terms([[a,b,c],[d,e,f],[a,h,i]]).
false.

定义all_different_terms/1还应该让您了解如何实现初始建议,重用compatible/2已定义的谓词:

all_compatible([]).
all_compatible([H|T]) :-
    maplist(compatible(H), T),
    all_compatible(T).