如何列出序言中具有特定数量后代的所有人?
How to list all people that have a specific number of descendants in prolog?
我可以检查 X 是否是 Y 的祖先,并且可以计算 X 有多少后代 我不知道如何列出所有拥有给定数量后代的人。当我把它放在规则中时,N = COUNT 不起作用。
parent(a,b).
parent(a,d).
parent(b,c).
parent(c,e).
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
?- aggregate_all(count, ancestor(a,_), COUNT). % output: COUNT = 4
?- aggregate_all(count, ancestor(b,_), COUNT). % output: COUNT = 2
?- aggregate_all(count, ancestor(c,_), COUNT). % output: COUNT = 1
?- aggregate_all(count, ancestor(d,_), COUNT). % output: COUNT = 0
?- aggregate_all(count, ancestor(e,_), COUNT). % output: COUNT = 0
% List all X that have N descendants
list_people(X,N) :-
是的,您必须编写一个更复杂的谓词,就像您开始时那样。一种可行的解决方案如下,尽管它需要一些关于它应该找到的原子的知识。这就是我添加 data([a,b,c,d,e])
事实的原因。
data([a,b,c,d,e]).
list_people(Res, N) :-
data(X),
aux(Res, X, N).
aux([], [], _).
aux([H|Res], [H|T], N) :-
findall(_, ancestor(H,_), List),
length(List, Count),
Count = N,
!,
aux(Res, T, N).
aux(Res, [_|T], N) :-
aux(Res, T, N).
另一种不需要“聚合”库的替代解决方案:
descendants(Person, N, Descendants) :-
setof(Descendant, ancestor(Person, Descendant), Descendants),
length(Descendants, N).
这个解决方案的有趣之处在于 setof/3
谓词为 Person
变量的每个绑定枚举了解决方案。
调用示例:
| ?- descendants(Person, N, Descendants).
Descendants = [b,c,d,e]
N = 4
Person = a ? ;
Descendants = [c,e]
N = 2
Person = b ? ;
Descendants = [e]
N = 1
Person = c
(1 ms) yes
请注意,基于 setof/3
,descendants/3
谓词对所有没有后代的人都无效。我们现在可以使用 findall/3
谓词来回答您的问题。例如,所有有 4 个后代的人:
| ?- findall(Person, descendants(Person,4,_), Persons).
Persons = [a]
yes
获取一个没有后代的人的列表怎么样?假设 person/1
谓词列出所有人(在 Marco 的回答中使用 data/1
谓词代替):
| ?- findall(Person, (person(Person), \+ descendants(Person,_,_)), Persons).
Persons = [d,e]
yes
我可以检查 X 是否是 Y 的祖先,并且可以计算 X 有多少后代 我不知道如何列出所有拥有给定数量后代的人。当我把它放在规则中时,N = COUNT 不起作用。
parent(a,b).
parent(a,d).
parent(b,c).
parent(c,e).
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
?- aggregate_all(count, ancestor(a,_), COUNT). % output: COUNT = 4
?- aggregate_all(count, ancestor(b,_), COUNT). % output: COUNT = 2
?- aggregate_all(count, ancestor(c,_), COUNT). % output: COUNT = 1
?- aggregate_all(count, ancestor(d,_), COUNT). % output: COUNT = 0
?- aggregate_all(count, ancestor(e,_), COUNT). % output: COUNT = 0
% List all X that have N descendants
list_people(X,N) :-
是的,您必须编写一个更复杂的谓词,就像您开始时那样。一种可行的解决方案如下,尽管它需要一些关于它应该找到的原子的知识。这就是我添加 data([a,b,c,d,e])
事实的原因。
data([a,b,c,d,e]).
list_people(Res, N) :-
data(X),
aux(Res, X, N).
aux([], [], _).
aux([H|Res], [H|T], N) :-
findall(_, ancestor(H,_), List),
length(List, Count),
Count = N,
!,
aux(Res, T, N).
aux(Res, [_|T], N) :-
aux(Res, T, N).
另一种不需要“聚合”库的替代解决方案:
descendants(Person, N, Descendants) :-
setof(Descendant, ancestor(Person, Descendant), Descendants),
length(Descendants, N).
这个解决方案的有趣之处在于 setof/3
谓词为 Person
变量的每个绑定枚举了解决方案。
调用示例:
| ?- descendants(Person, N, Descendants).
Descendants = [b,c,d,e]
N = 4
Person = a ? ;
Descendants = [c,e]
N = 2
Person = b ? ;
Descendants = [e]
N = 1
Person = c
(1 ms) yes
请注意,基于 setof/3
,descendants/3
谓词对所有没有后代的人都无效。我们现在可以使用 findall/3
谓词来回答您的问题。例如,所有有 4 个后代的人:
| ?- findall(Person, descendants(Person,4,_), Persons).
Persons = [a]
yes
获取一个没有后代的人的列表怎么样?假设 person/1
谓词列出所有人(在 Marco 的回答中使用 data/1
谓词代替):
| ?- findall(Person, (person(Person), \+ descendants(Person,_,_)), Persons).
Persons = [d,e]
yes