Prolog 从列表中删除所有增加的子系列

Question

任务是从列表中删除所有递增的子序列。例如： deleteInc([2,4,6,5,8,12,8,3],L) 应该产生 L=[8,3] 作为结果

我试图解决它，但它无法正常工作，我无法找出正确的解决方案。有人可以用正确的解决方案帮助我吗？提前致谢:)

我的代码：

deleteInc([],[]).
deleteInc([H1,H2|T],L):-
    H2>=H1,
    !,
    deleteInc(T,L).
deleteInc([H1,H2|T],[H2|T2]):-
    H2<H1,
    deleteInc(T,T2).

Answer 1

这是我所做的，假设它一次检查三个值：

deleteInc([],[]).
deleteInc([H1,H2,_H3|T],L):-
    H2>=H1,
    !,
    deleteInc(T,L).
deleteInc([H1,H2|T],[H1,H2|T2]):-
    H2<H1,!,
    deleteInc(T,T2).

示例：

?-deleteInc([2,4,6,5,8,12,8,3],L).
L = [8, 3]

?-deleteInc([2,4,6,5,8,12,15,21,25,7,3],L).
L = [7, 3]

?-deleteInc([2,4,6,5,8,12,15,21,25,55,77,88,65,38],L).
L = [65, 38]

这是一种收集所有不增加的组合的方法：

deleteInc(L,[],L).
deleteInc([H1,H2|T],L,Rest):-
    H2>=H1,
    !,
    deleteInc(T,L,Rest).
deleteInc([H1,H2|T],[H1,H2|L],Rest):-
    H2<H1,!,
    deleteInc(T,L,Rest).

示例：-

?-deleteInc([2,4,6,5,8,12,15,21,25,55,77,88,65,38],L,_).
L = []
L = []
L = [6, 5]
L = [6, 5]
L = [6, 5]
L = [6, 5]
L = [6, 5]
L = [6, 5, 65, 38]

?-deleteInc([2,4,6,5,8,12,15,21,25,7,3],L,_).
L = []
L = []
L = [6, 5]
L = [6, 5]
L = [6, 5]
L = [6, 5, 25, 7]

?-deleteInc([2,4,6,5,8,12,8,3],L,_).
L = []
L = []
L = [6, 5]
L = [6, 5]
L = [6, 5, 8, 3]

Answer 2

我会这样实现：

deleteInc(In, Out):-
    deleteInc(In,Out,new).

deleteInc([A],[A],new).
deleteInc([_],[],incr).
deleteInc([H1,H2|T],L,_):-
    H2>=H1,
    !,
    deleteInc([H2|T],L,incr).
deleteInc([H1,H2|T],T2,incr):-
    H2<H1,
    deleteInc([H2|T],T2,new).
deleteInc([H1,H2|T],[H1|T2],new):-
    H2<H1,
    deleteInc([H2|T],T2,new).

第三个属性表示您当前是否处于 new 或 incr 缓和状态。

如果列表的两个头元素是递增顺序，第三个元素几乎被忽略。请注意不要转发列表 T，而是转发 [H2|T]，因为您需要元素 H2 进行进一步比较。如果你在连胜中（incr）并且当前两个头部元素没有增加，你和以前一样：忽略。但是，如果您刚刚开始 new 连胜并且当前头部元素正在减少，则将第一个头部元素放入 return 列表中。一个元素的特殊情况。让我们检查一下：

?- deleteInc([2,4,6,5,8,12,8,3],L).
L = [8, 3] ;
false.

看起来不错。

Answer 3

另一种方法是只检查 3 个连续的元素，如果中间的元素小于第一个但大于第三个。如果是这种情况：存储元素。如果不是这种情况：检查没有第一个头元素的列表。

为剩下的 2 个元素添加规则。还需要对第一个元素进行特殊处理，因为这在主要规则中没有涉及。通过使用剪切，您可以在最后一行“捕获”剩余的大小写（两个递增的元素或带有一个或没有元素的奇怪输入）。请注意，规则的顺序对于程序的运行很重要。

deleteInc([H1,H2|L], [H1|R]):-
    H1 >= H2,
    !,
    deleteInc1([H1,H2|L], R).
deleteInc([H1,H2|L], R):-
    deleteInc1([H1,H2|L], R).

deleteInc1([H1,H2,H3|L], [H2|R]):-
    H1 > H2,
    H2 > H3,
    !,
    deleteInc1([H2,H3|L], R).
deleteInc1([A,B],[B]):-
    A > B,
    !.
deleteInc1([_|L], R):-
    !,
    deleteInc1(L, R).
deleteInc1(_,[]).

我们来测试一下：

?- deleteInc([2,4,6,5,8,12,8,3],L).
L = [8, 3].

有效（用于数字列表）。

Answer 4

另一种解决方案是计算条纹的长度并过滤掉所有包含多个元素的结果。以下代码从第一个元素的计数 0 开始，并使用后继谓词 s/1 进行计数：

deleteInc(In, Out):-
    countInc(In,0,InC),
    delInc(InC,Out).

countInc([A], C, [(A,C)]).
countInc([A,B|L], C, Out):-
    A =< B,
    countInc([B|L], s(C), Out).
countInc([A,B|L], C, [(A,C)|Out]):-
    A > B,
    countInc([B|L], 0, Out).
    
delInc([],[]).
delInc([(E,0)|L],[E|R]):-
    delInc(L,R).
delInc([(_,s(_))|L],R):-
    delInc(L,R).

输出：

?- deleteInc([2,4,6,5,8,12,8,3],L)
L = [8, 3] ;
false.

符合预期

Prolog 从列表中删除所有增加的子系列

Prolog delete all increasing subseries from a list

list

prolog

series