的Prolog - 除去非独特元素
我有一个谓词来检查元件是列表的成员,并期待如下:的Prolog - 除去非独特元素
member(X,[X|_]).
member(X,[_|T]) :- member(X,T).
当我打电话: - 部件(1,[2,3, 1,4]) 我得到:true。
而现在我必须用它来写谓词将从列表中的列表中删除所有非唯一元素,如下列:
remove([[a,m,t,a],[k,a,w],[i,k,b,b],[z,m,m,c]],X).
X = [[t],[w],[i,b,b],[z,c]]
我怎么能这样做?
以您的示例和@ false的评论为例,实际问题似乎是从每个子列表中删除发生在任何其他子列表中的元素。我的困难将其概念化为单词,导致我构建了我认为是非常混乱和粗糙的一段代码。
所以首先我想要一个小助手谓词排序member/2
直到列表子列表。
in_sublist(X, [Sublist|_]) :- member(X, Sublist).
in_sublist(X, [_|Sublists]) :- in_sublist(X, Sublists).
这是没有很大的一块工作,并于实话我觉得,因为我只是不能看到自己曾经想使用这个对自己应该以某种方式内联。
现在,我最初的解决方案是不正确的,看起来像这样:
remove([Sub1|Subs], [Res1|Result]) :-
findall(X, (member(X, Sub1), \+ in_sublist(X, Subs)), Res1),
remove(Subs, Result).
remove([], []).
你可以看到那种主题的我要去这里虽然:让我们用findall/3
枚举子列表的元素在这里然后我们可以过滤掉其他列表中出现的那些。这并不完美,输出看起来像这样。
?- remove([[a,m,t,a],[k,a,w],[i,k,b,b],[z,m,m,c]], R).
R = [[t], [a, w], [i, k, b, b], [z, m, m, c]].
所以,它开始寻求与[t]
OK,但随后失去与[a,w]
的情节,因为没有可视性输入[a,m,t,a]
当我们到达第一个递归调用。有几种方法可以处理它;一个聪明的人可能会形成一种拉链,我们将列表中的前面的元素和后面的元素放在一起。另一种方法是在递归调用之前从所有后续列表中删除列表中的元素。我选择了一个“更简单”的解决方案,该解决方案更加复杂,难以阅读,但花费的时间更少。我强烈建议您调查其他可读性选项。
remove(In, Out) :- remove(In, Out, []).
remove([Sub1|Subs], [Res1|Result], Seen) :-
findall(X, (member(X, Sub1),
\+ member(X, Seen),
\+ in_sublist(X, Subs)), Res1),
append(Sub1, Seen, Seen1),
remove(Subs, Result, Seen1).
remove([], [], _).
所以基本上现在我保持一个“看到”列表。在递归调用之前,我把目前为止所看到的东西以及这个列表中的元素缝合在一起。这不是特别有效,但它似乎完成了这项工作:
?- remove([[a,m,t,a],[k,a,w],[i,k,b,b],[z,m,m,c]], R).
R = [[t], [w], [i, b, b], [z, c]].
这让我觉得很讨厌的问题。老实说,我很惊讶这是多么令人讨厌。我希望别人能够走到一起,找到更好的解决方案。
要调查的另一件事是DCGs,这可以帮助做这些类型的列表处理任务。
使用library(reif)
为 SICStus | SWI:
lists_uniques(Xss, Yss) :-
maplist(tfilter(in_unique_t(Xss)), Xss, Yss).
in_unique_t(Xss, E, T) :-
tfilter(memberd_t(E), Xss, [_|Rs]),
=(Rs, [], T).
注,虽然没有限制如何命名谓语,非关系,必须经常名称背后隐藏的纯关系。 remove
是一个真正的必要条件,但我们只想要一个关系。列表列表与仅具有唯一元素的列表列表之间的关系。
使用示例:
?- lists_uniques([[X,b],[b]], [[X],[]]).
dif(X, b).
因此,在这种情况下,我们都留下X
一个非实例变量。因此,Prolog计算可能的最一般的答案,找出X
的样子。
(请注意,已经接受不正确的回答在这种情况下失败)
为什么'X = [[T],[K,W],[I,B,B],[Z,C]] '?在[[a,m,t,a],[k,a,w],[i,k,b,b],[z,m,m,c]]'和'b在解决方案中出现两次。这没有多大意义。 – lurker
抱歉,这是我的错误 – user
@lurker:'b,b'在这里是因为它只出现在一个子列表中 - 大概是 – false