删除列表中的重复项(Prolog) [英] Remove duplicates in list (Prolog)

问题描述

我对 Prolog 完全陌生，并尝试了一些练习.其中之一是:

I am completely new to Prolog and trying some exercises. One of them is:

写一个谓词集(InList,OutList)它将任意输入作为输入列表，并返回一个列表，其中每个输入列表的元素只出现一次.

Write a predicate set(InList,OutList) which takes as input an arbitrary list, and returns a list in which each element of the input list appears only once.

这是我的解决方案:

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

set([],[]).
set([H|T],[H|Out]) :-
    not(member(H,T)),
    set(T,Out).
set([H|T],Out) :-
    member(H,T),
    set(T,Out).

我不允许使用任何内置谓词(最好不要使用 not/1).问题是，set/2 提供了多个 same 解决方案.输入列表中的重复次数越多，产生的解决方案就越多.我究竟做错了什么?提前致谢.

I'm not allowed to use any of built-in predicates (It would be better even do not use not/1). The problem is, that set/2 gives multiple same solutions. The more repetitions in the input list, the more solutions will result. What am I doing wrong? Thanks in advance.

推荐答案

由于 Prolog 的回溯，您得到了多个解决方案.从技术上讲，提供的每个解决方案都是正确的，这就是生成它的原因.如果您只想生成一个解决方案，您将不得不在某个时候停止回溯.这就是 Prolog cut 的用途.您可能会发现阅读这些内容可以帮助您解决这个问题.

You are getting multiple solutions due to Prolog's backtracking. Technically, each solution provided is correct, which is why it is being generated. If you want just one solution to be generated, you are going to have to stop backtracking at some point. This is what the Prolog cut is used for. You might find that reading up on that will help you with this problem.

更新:没错.如果第一个变量在第二个变量中的多个位置，则您的 member() 谓词以几种不同的方式评估为 true.

Update: Right. Your member() predicate is evaluating as true in several different ways if the first variable is in multiple positions in the second variable.

我为这个谓词使用了名称 mymember()，以免与 GNU Prolog 的内置 member() 谓词冲突.我的知识库现在看起来像这样:

I've used the name mymember() for this predicate, so as not to conflict with GNU Prolog's builtin member() predicate. My knowledge base now looks like this:

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

not(A) :- + call(A).

set([],[]).
set([H|T],[H|Out]) :-
    not(mymember(H,T)),
    set(T,Out).
set([H|T],Out) :-
    mymember(H,T),
    set(T,Out).

因此，mymember(1, [1, 1, 1]). 以三种不同的方式评估为 true:

So, mymember(1, [1, 1, 1]). evaluates as true in three different ways:

| ?- mymember(1, [1, 1, 1]).

true ? a

true

true

no

如果你只想得到一个答案，你将不得不使用一个cut.将 mymember() 的第一个定义更改为:

If you want to have only one answer, you're going to have to use a cut. Changing the first definition of mymember() to this:

mymember(X,[X|_]) :- !.

解决您的问题.

此外，如果您愿意，您可以通过自己定义一个 notamember() 谓词来完全避免 not().选择权在你.

Furthermore, you can avoid not() altogether, if you wish, by defining a notamember() predicate yourself. The choice is yours.

这篇关于删除列表中的重复项(Prolog)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！