logo标签列表

Prolog代码将列表的部分分割为连续的偶数部分和奇数部分

prolog
3
我收到了以下问题： 任何整数列表都可以（唯一地）被分成“奇偶运行”，其中每个运行是原始列表中连续偶数或奇数的（最大）序列。例如，列表 List = [8,0,4,3,7,2,-1,9,9] 可以被分为[8, 0, 4]、[3, 7]、[2]和[-1, 9, 9]。 编写一个谓词paruns(List, RunList)，将数字列表转换为相应的奇偶运行列表。例如：
?- paruns([8,0,4,3,7,2,-1,9,9], RunList).
RunList = [[8, 0, 4], [3, 7], [2], [-1, 9, 9]]

以下是我尝试的代码，对于上面的示例情况似乎可以工作，感谢一个建议。但是当我运行paruns([8,0,4], RunList)时，它会打印出RunList = [[8,0,4],[]]。任何建议将不胜感激 :)

paruns([],[]).
paruns([Head | Tail], [E, O | S]) :-
   even([Head | Tail], E, Last),
   odd(Last, O, Last1),
   paruns(Last1, S).

even([Head | Tail], [], [Head | Tail]) :-
   Head mod 2 =:= 1.
even([Head | Tail], [Head | L], Last) :-
   Head mod 2 =:= 0,
   even(Tail, L, Last).
even([],[],[]).

odd([Head | Tail], [], [Head, Tail]) :-
   Head mod 2 =:= 0.
odd([Head | Tail], [Head | L], Last) :-
   Head mod 2 =:= 1,
   odd(Tail, L, Last).
odd([],[],[]).
3个回答
4

TL;DR: 找到 split_if_adj/3 中的“洞”的“正确卡榫”，问题就解决了！

这个答案基于：

因此，基本上我们将递归处理列表的繁琐且有时棘手的任务委托给高阶谓词，我们适当地自定义它。
示例查询：
?- split_if_adj(dif_parity_t, [8,0,4,3,7,2,-1,9,9], Rss).
Rss = [[8,0,4],[3,7],[2],[-1,9,9]].

请注意，上述查询具有确定性成功的特点。
4
Prolog的一个主要吸引力是其关系性质。这意味着，如果只使用足够通用的基元，我们经常可以在多个方向上使用Prolog谓词。在这种情况下，由于您正在推理整数，我强烈建议您使用Prolog系统的CLP(FD)约束来受益于此种普遍性。有关此重要的声明性特性的更多信息，请参见。
此外，由于您正在描述一个列表，请考虑使用DCG表示法（）。
以下是您的任务的关系解决方案： 
parity_runs([], [])     --> [].
parity_runs([E|Es], Os) --> [E], { E mod 2 #= 0 }, parity_runs(Es, Os).
parity_runs(Es, [O|Os]) --> [O], { O mod 2 #= 1 }, parity_runs(Es, Os).

我们可以将它用于您发布的测试用例，其中指定了列表:

?- phrase(parity_runs(Es, Os), [8,0,4,3,7,2,-1,9,9]).
Es = [8, 0, 4, 2],
Os = [3, 7, -1, 9, 9] ;
false.

此外，我们还可以在其他方向上使用它。例如，假设已知runs，但未知列表:

?- phrase(parity_runs([2,4], [1,3]), Ls).
Ls = [2, 4, 1, 3] ;
Ls = [2, 1, 4, 3] ;
Ls = [2, 1, 3, 4] ;
Ls = [1, 2, 4, 3] ;
Ls = [1, 2, 3, 4] ;
Ls = [1, 3, 2, 4] ;
false.

此外，我们还可以发布最通用的查询，其中没有任何已知信息：

?- phrase(parity_runs(Es, Os), Ls).
Es = Os, Os = Ls, Ls = [] ;
Es = Ls, Ls = [_2012],
Os = [],
_2012 mod 2#=0 ;
Es = Ls, Ls = [_256, _258],
Os = [],
_256 mod 2#=0,
_258 mod 2#=0 ;
Es = Ls, Ls = [_826, _832, _838],
Os = [],
_826 mod 2#=0,
_832 mod 2#=0,
_838 mod 2#=0 ;
等。
为了公平地列举答案，我们可以使用迭代加深搜索： 
？- length（Ls，_），phrase（parity_runs（Es，Os），Ls）。
Ls = Es，Es = Os，Os = [];
Ls = Es，Es = [_ 168]，
Os = []，
_ 168 mod 2＃= 0;
Ls = Os，Os = [_ 550]，
Es = []，
_ 550 mod 2＃= 1;
Ls = Es，Es = [_ 770，_ 776]，
Os = []，
_ 770 mod 2＃= 0，
_ 776 mod 2＃= 0;
Ls = [_ 770，_ 776]，
Es = [_ 770]，
Os = [_ 776]，
_ 770 mod 2＃= 0，
_ 776 mod 2＃= 1;
等等。
2
谢谢你的所有建议，今天我实际上去学习了关于clpfd的知识，我可以看到它有很多用途！我刚刚开始学习Prolog，从C语言来看，这是一个相当大的差异，但是你的写作非常有教育意义！再次感谢！ :) - Iza
3

我认为你只是打错了字，第一个odd/3子句。以下是代码:

paruns([],[]).
paruns([Head | Tail], [E, O | S]) :-
   even([Head | Tail], E, Last),
   odd(Last, O, Last1),
   paruns(Last1, S).

even([Head | Tail], [], [Head | Tail]) :-
   Head mod 2 =:= 1.
even([Head | Tail], [Head | L], Last) :-
   Head mod 2 =:= 0,
   even(Tail, L, Last).
even([],[],[]).

odd([Head | Tail], [], [Head | Tail]) :-  % corrected
   Head mod 2 =:= 0.
odd([Head | Tail], [Head | L], Last) :-
   Head mod 2 =:= 1,
   odd(Tail, L, Last).
odd([],[],[]).

我明白了

?- paruns([8,0,4,3,7,2,-1,9,9], RunList).
RunList = [[8, 0, 4], [3, 7], [2], [-1, 9, 9]]

编辑

一种丢弃空序列的可能性（我认为这只会发生在第一个或最后一个位置...所以也许更好的方法是对这些情况进行结果清理）：

paruns([],[]).
%paruns([Head | Tail], [E, O | S]) :-
paruns([Head | Tail], R) :-
   even([Head | Tail], E, Last),
   odd(Last, O, Last1),
    (E=[] -> R=[O|S] ; O=[] -> R=[E|S] ; R=[E,O|S]),
   paruns(Last1, S).
非常感谢，我不知道为什么我没看到那个，现在我只有一个小问题，如果你能帮忙的话。当我用上面的例子运行它时，它得到了完美的输出，但是当我使用 'paruns([8,0,4], RunList).' 时，它打印出 RunList = [[8,0,4],[]]。如何修复这个问题？？再次感谢 :) - Iza
抱歉，更简单的“解决方案”会导致代码难看。无论如何，请查看我的编辑... - CapelliC
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接