在 Prolog 中少列出

Question

我想为 2 个列表 list_less(L1, L2) 编写一个谓词，如果列表 L1 小于列表 L2，就以下顺序而言，该谓词为真：

list_less(L1, L2) iff  
 Let L1' := complement(L1,L2), L2' := complement(L2,L1)  
  (complement(L1,L2) contains those elements of L1  
   that are not in L2)  
 Let m1 := max(L1'), m2 := max(L2')  
  (max(L) gives the maximal element of L with respect to  
   the standard order @<)  
 m1 @< m2.

输出是这样的：

?- list_less([3,3,3,3,2,2],[3,3,4,0]).
true.

?- list_less([a,b,X,Y,[X|Y],2], [[X,X|Y]]).
true.

?- list_less([a,b,X,Y,[X|Y],2], [X,b,b]).
false.

我是从这个开始的：

list_less([],[]).
list_less([H|T],[X|Y]):-
    complement([H|T],[X|Y],L),
    max_list(H|T],M1).

complement([],[],[]). 
complement([H|T],[X|Y],L):-
    member(H,[X|Y]),
    !,
    complement(T,Y,[X|_]).

max_list(L, Max):-
    select(Max, L, Rest),
    \+ (member(E, Rest), E > Max).

Answer 1

这是一个更紧凑的解决方案（比先计算差异列表的解决方案）。

list_less(As, Bs):-
    sort(As, SortedAs),
    reverse(SortedAs, RevAs),
    sort(Bs, SortedBs),
    reverse(SortedBs, RevBs),
    RevAs @< RevBs.

两个列表先排序倒序再比较w.r.t。术语的标准顺序。这意味着元素是从左边开始比较的。因此，前两个不同的元素（对应于每个列表中未出现在另一个列表中的最大元素）将使比较成功或失败。这是有效的，因为 sort/2 也删除了重复项。

| ?- list_less([3,3,3,3,2,2],[3,3,4,0]).

(4 ms) yes
| ?- list_less([a,b,X,Y,[X|Y],2], [[X,X|Y]]).

yes
| ?- list_less([a,b,X,Y,[X|Y],2], [X,b,b]).

no

在 Prolog 中少列出

List less in Prolog

prolog