Prolog - 删除非唯一元素 [英] Prolog - remove the non unique elements

问题描述

我有一个谓词来检查元素是否是列表的成员并如下所示:

I have a predicate to check if the element is member of list and looks the following:

member(X,[X|_]).
member(X,[_|T]) :- member(X,T).

当我打电话时: ?- member(1,[2,3,1,4])我得到:真的.

When I called: ?- member(1,[2,3,1,4]) I get: true.

现在我必须用它来编写谓词，它将从列表中删除所有非唯一元素，如下所示:

And now I have to use it to write predicate which will remove all non unique elements from list of lists like the following:

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 的评论，实际问题似乎类似于从任何其他子列表中出现的每个子列表中删除元素.我难以将其概念化为文字，这导致我构建了一段我认为非常混乱和粗俗的代码.

Going by your example and @false's comment, the actual problem seems to be something like removing elements from each sublist that occur in any other sublist. My difficulty conceptualizing this into words has led me to build what I consider a pretty messy and gross piece of code.

所以首先我需要一个辅助谓词来将 member/2 移动到子列表列表.

So first I want a little helper predicate to sort of move member/2 up to lists of sublists.

in_sublist(X, [Sublist|_])  :- member(X, Sublist).
in_sublist(X, [_|Sublists]) :- in_sublist(X, Sublists).

这不是什么伟大的作品，事实上我觉得它应该以某种方式内联，因为我看不到自己想要单独使用它.

This is no great piece of work, and in truth I feel like it should be inlined somehow because I just can't see myself ever wanting to use this on its own.

现在，我最初的解决方案不正确，看起来像这样:

Now, my initial solution wasn't correct and looked like this:

remove([Sub1|Subs], [Res1|Result]) :-
    findall(X, (member(X, Sub1), \+ in_sublist(X, Subs)), Res1),
    remove(Subs, Result).
remove([], []).

你可以在这里看到我想要的那种主题:让我们使用 findall/3 在这里枚举子列表的元素，然后我们可以过滤掉出现在其他列表.这并不能解决问题，输出看起来像这样.

You can see the sort of theme I'm going for here though: let's use findall/3 to enumerate the elements of the sublist in here and then we can filter out the ones that occur in the other lists. This doesn't quite do the trick, the output looks like this.

?- 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] 看起来不错，但随后使用 [a,w] 丢失了绘图，因为输入 不可见[a,m,t,a] 当我们到达第一个递归调用时.我们可以通过多种方式处理它；一个聪明的方法可能是形成一种拉链，我们将列表的前面元素和后面的元素放在一起.另一种方法是在递归调用之前从所有后续列表中删除此列表中的元素.我选择了一个更简单"的解决方案，它更混乱、更难阅读，但花费的时间更少.我强烈建议您调查其他选项以提高可读性.

So, it starts off looking OK with [t] but then loses the plot with [a,w] because there is not visibility into the input [a,m,t,a] when we get to the first recursive call. There are several ways we could deal with it; a clever one would probably be to form a sort of zipper, where we have the preceding elements of the list and the succeeding ones together. Another approach would be to remove the elements in this list from all the succeeding lists before the recursive call. I went for a "simpler" solution which is messier and harder to read but took less time. I would strongly recommend you investigate the other options for readability.

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([], [], _).

所以基本上现在我保留了一个见过"的清单.就在递归调用之前，我将迄今为止看到的内容和此列表的元素拼接在一起.这不是特别有效，但似乎可以完成工作:

So basically now I'm keeping a "seen" list. Right before the recursive call, I stitch together the stuff I've seen so far and the elements of this list. This is not particularly efficient, but it seems to get the job done:

?- 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]].

这让我觉得这是一个非常讨厌的问题.老实说，我很惊讶它有多讨厌.我希望其他人能找到一个更好的解决方案，读起来更好.

This strikes me as a pretty nasty problem. I'm surprised how nasty it is, honestly. I'm hoping someone else can come along and find a better solution that reads better.

另一件需要调查的事情是 DCG，它可以帮助完成这些类型的列表处理任务.

Another thing to investigate would be DCGs, which can be helpful for doing these kinds of list processing tasks.

这篇关于Prolog - 删除非唯一元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！