使用Prolog获取列表中偶数的最长子序列

Question

我想实现一个谓词longest_even_sequence(X,Y)，其中X是给定的列表，Y是一个return是最长的偶数子序列的列表。例如对于给定的列表 2,4,6,3,5,2,2 我想 return 2,4,6.

这是我试过的代码，但我不知道如何让它工作（我是 Prolog 的初学者）

longest_even_sequence([],[]).
longest_even_sequence([H|T],[R]):-
    H mod 2 =:= 0,
    longest_even_sequence(T,R1)
    R is [H|R1]                .
longest_even_sequence([H|T],[]):-
    H mod 2 =\= 0,
    longest_even_sequence(T,R2),
    R2 is [].

Answer 1

老实说，这是一项相当 beginner-unfriendly 的任务，因为它没有直接指出 prolog 的优点，并且在使用递归方法时存在多个问题。

第一次尝试：添加一个参数。以基本的递归方式进行操作需要您添加一个参数来保持您当前的连胜记录，以便将其与您当前的最佳记录进行比较。这需要引入一个新的谓词并且似乎是使用递归的最简单的 beginner-friendly 解决方案。为了不给自己太大压力，我使用 if-then-else ( ... -> ... ; ...) 来处理 maximum-chosing。基本思想是遍历列表并在第二个参数中收集连胜。一旦我遇到一个奇数，我就得到列表其余部分的最大偶数子序列 (longest_even_sequence(T,[],Rtmp)) 并将其与当前连胜 (LT > LR) 进行比较。较大的列表将被复制到输出参数。一旦我到达终点，我就复制我当前的连续记录 (longest_even_sequence([],R,R).)。

这一个的潜在问题是条纹的顺序是相反的，因此您需要将其反转。同样使用 if-then-else 不是 beginner-level。以连胜收场，以连胜结束，没问题。

longest_even_sequence(In,Out) :-
    longest_even_sequence(In,[],ROut),
    reverse(ROut,Out).

longest_even_sequence([],R,R).
longest_even_sequence([H|T],Tmp,R):-
    H mod 2 =:= 0,
    longest_even_sequence(T,[H|Tmp],R).
longest_even_sequence([H|T],Tmp,R):-
    H mod 2 =\= 0,
    longest_even_sequence(T,[],Rtmp),
    length(Rtmp,LR),
    length(Tmp,LT),
    (
        LT > LR
    ->  R = Tmp
    ;   R = Rtmp
    ).

使用 SWISH 测试：

?- longest_even_sequence([2,4,6,2,3,4,5,4,4,4,5,6],R).
R = [2, 4, 6, 2]; 
false.

只是为了好玩（是的，我是认真的），让我们用另一种更复杂和计算密集型的方式来做：

range(High, _, High).
range(Out,Low,High) :- 
    NewH is High-1, 
    NewH >= Low, 
    range(Out, Low, NewH).

alleven([]).
alleven([H|T]):-
    H mod 2 =:= 0,
    alleven(T).

les(In,Out):-
    length(In,Lin),
    range(N,0,Lin),
    length(Out,N),
    append(_,InRest,In),
    append(Out,_,InRest),
    alleven(Out), 
    !.

测试：

?- les([2,4,6,2,3,4,5,4,4,4,5,6],R).
R = [2, 4, 6, 2].

那么会发生什么？首先按降序生成 0 和输入列表长度之间的数字（使用 range(N,0,Lin)，修改后的代码来自 here）。然后创建一个包含 N（未知）元素的列表 length(Out,N),。然后输入列表 In 被分成 3 部分，开始和结束并不重要，但中间必须有 N 个元素，这是通过将其与 Out 统一来强制执行的，这是一个包含 N 个元素的列表。此列表必须包含所有偶数。如果成功，则跳过所有其他答案（!，称为剪切，更高级的序言）。如果不成功，则测试下一个合适的子列表。如果没有匹配长度 N 的列表，则测试下一个较低的 N 直到您最终达到 N=0.

Answer 2

我现在已经投票了，但我想推荐 foldl，有一个转折：

is_even(Stop, ListElement, Ittr, Result) :-
    ((ListElement mod 2) =:= 0 , \+(\+(Stop=0)), \+(\+(Stop=1)) ->  
        append(Ittr, [ListElement], Result) ;
        Stop is 1, Result = Ittr
    ).

longest_even_sequence(List, Result) :-
    foldl(is_even(_), List, [], Result).

longest_even_sequence([2,4,6,1,5,3,2,1], 结果)

结果 = [2, 4, 6]

使用Prolog获取列表中偶数的最长子序列

Getting longest subsequence of even numbers in a list with Prolog

prolog