我在递归搜索列表和根据结果创建列表列表时遇到问题..
知识库包含球队名称、获胜次数和他们所在的区域,所有这些都与他们的球队编号相关联。我正在传递 Teams
中的团队编号列表,并且正在使用 findMinMax/3
搜索匹配对。我需要的结果是...
配对团队列表列表(例如 X = [[gonzaga, washington], [iowa, oklahoma], …]
)
和 1 个不匹配的团队(由奇数个团队产生)或 0 个(在偶数的情况下)
我想通了其他一切,并且可以达到 [gonzaga, washington]
部分,但在递归部分失败...
findPair(Teams,[HL|TL],Rest) :-
findMinMax(Teams,Min,Max),
delete(Teams,Min,TeamsNoMin),
delete(TeamsNoMin,Max,Rest),
createPair(Min,Max,Pair), %Pair = "["Min_team","Max_team"]"
append(HL,[Pair],TL),
findPair(Rest,TL,[]).
最佳答案
一个通用的递归方案
在这里,我将尝试向您展示我们通常如何在 Prolog 中执行递归。这对初学者来说并不容易,因为列表是“反向”构建的:在我们到达列表末尾之前,什么都没有真正构建。
这个“向后构建”原则的原因是,一旦设置了一个变量,就不能将它设置为另一个值,所以例如很难说结果是 [1]
在递归的第一步,然后变成 [1, 2]
。相反,我们在 Prolog 中说的是结果头是 1
,结果尾是递归调用的结果(是的,如果它变得困惑,请读两遍:d)。因此,只要我们不遇到基本情况(不执行递归的情况),我们就不会明确绑定(bind)变量(即我们总是让部分术语未绑定(bind))。
对于谓词 rec/2: rec(Input, Result)
通过将输入列表的元素与 somepredicate/2
链接起来从输入列表中生成结果列表,我们将写:
rec([InputHead|InputTail], [ResultHead|ResultTail]) :-
somepredicate(InputHead, ResultHead),
rec(InputTail, ResultTail).
代表那个。
在这里您可以看到我们声明结果的头部是 ResultHead
并且它的尾部是通过调用 rec(InputTail, ResultTail) 计算的。
现在很好,但我们需要在某个时刻停止,例如,当列表为空时。我们会这样写:
rec([], []).
这意味着:当输入列表为空时,结果列表也是空的。
对你的谓词的应用
现在,要解决您的问题,您首先必须修复递归子句:
findPair(Teams,[HL|TL],Rest) :-
findMinMax(Teams,Min,Max),
delete(Teams,Min,TeamsNoMin),
delete(TeamsNoMin,Max,Rest),
createPair(Min,Max,Pair), %Pair = "["Min_team","Max_team"]"
append(HL,[Pair],TL),
findPair(Rest,TL,[]).
会变成
findPair(Teams, [Pair|Tail], LeftOver) :-
findMinMax(Teams, Min, Max),
delete(Teams, Min, TeamsNoMin),
delete(TeamsNoMin, Max, Rest),
createPair(Min, Max, Pair), %Pair = "["Min_team","Max_team"]"
findPair(Rest, Tail, LeftOver).
需要注意的重要一点:现在 Rest
已经变成了两个独立的变量。 findPair/3
的最后一个参数不再改变,因为在递归调用中我们还不知道任何关于它的信息,所以我们不能绑定(bind)它,并且 in-predicate Rest
因此现在是独立的,只代表尚未处理的团队,因此对我们结果列表的尾部(以及 LeftOver
)感兴趣。
现在我们必须处理基本情况:
没有队伍时
findPair([], [], []).
这里我们说当
Teams
为空时,Result
和LeftOver
也为空。当只剩下一个团队时
findPair([Last], [], [Last]).
这里我们说当
Teams
只有一个元素时,LeftOver
等于Teams
,Result
是空。
结果代码是:
findPair([], [], []).
findPair([Last], [], [Last]).
findPair(Teams, [Pair|Tail], LeftOver) :-
findMinMax(Teams, Min, Max),
delete(Teams, Min, TeamsNoMin),
delete(TeamsNoMin, Max, Rest),
createPair(Min, Max, Pair), %Pair = "["Min_team","Max_team"]"
findPair(Rest, Tail, LeftOver).
要使您的子句具有排他性,您可以将 Teams
替换为 [Not, Empty|AtAll]
以确保最后一个子句仅用于长度为 2 或更长的列表,或者只是在子句的开头添加一个守卫,例如 Teams = [_, _|_],
。
希望它有所帮助,不要犹豫,在评论中要求澄清:)
关于list - Prolog - 递归调用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12030515/