2

如何在 Prolog 中的列表中搜索多次出现的特定元素？

例如，如果我们在列表中搜索[1,2,3,4,1]元素1，Prolog 应该返回true，否则会返回false所有其他数字。

这是我到目前为止所拥有的：

duplicate([], _) :-
   false,
   !.
duplicate([X|_], X) :-
   true,
   !.
duplicate([H|T], X) :-
   T = [_|T1],
   duplicate(T, X),
   duplicate(T1, X).

我的基本想法是搜索列表，直到找到我要查找的元素，然后再次在列表的尾部搜索该项目。我不想使用 Prolog 提供的 member() 函数。

如果查询询问，Prolog 还应该返回多次出现的元素：duplicate([1,2,3,4,1], X)，应该打印X = 1。

4

5 回答 5

3

我在评论中说的是：我想要列表 L 中的两个项目不在同一个地方，所以

duplicate(L, V) :-

   % nth0 gives the index (from 0) of an element in a list
   % element V is at the place Id1 in L
   nth0(Id1, L, V),
   % element V is at the place Id2 in L
   nth0(Id2, L, V),
   % Id1 is different from Id2
   % It is more usefull to say that Id1 < Id2
   % Thanks **false** for the improvement
   Id1 < Id2.

另一种方法是说：我删除列表的元素（这是在 SWI-Prolog 中通过 select/3 完成的）并检查它是否在列表的其余部分中：

duplicate(L, V) :-
    select(V, L, L1),
    member(V, L1).
于 2014-08-24T13:56:40.980 回答
3

这里是使用语法的明显版本。从某种意义上说，我们正在描述包含重复项的列表的结构。该结构如下：

  • 首先，有任何东西（...），
  • 然后是元素 ( [V])，
  • 再次任何（...）
  • 又是元素 ( [V])
  • 其次是任何东西。
duplicate(L, V) :-
   phrase(( ..., [V], ..., [V], ... ), L).

... --> [] | [_], ... .

不利的一面是，此版本将为类似的查询生成冗余答案

?- duplicate([a,a,a],a).

这可以通过使用来克服dif/2：

duplicate(L, V) :-
   phrase(( all(dif(V)), [V], all(dif(V)), [V], ... ), L).

非终端的定义all//1。

于 2014-08-24T17:10:44.710 回答
3

纯粹而简单！使用具有具体化术语相等 ，如下所示：tcount/3(=)/3

?- tcount(=(X), [1,2,3,4,1], 2).
X = 1 ;                              % succeeds, but leaves choicepoint
false.

?- tcount(=(1), [1,2,3,4,1], 2).
true.                                % succeeds deterministically

?- tcount(=(X), [b,c,d,a,b,a,c], 2).
X = b ;
X = c ;
X = a ;
false.

?- tcount(=(a), [b,c,d,a,b,a,c], 2).   
true.                                % succeeds deterministically

最后，让我们运行以下非常通用的查询：

?- tcount(=(a), Ls, 2).
Ls = [a,a]                                           ;
Ls = [a,a,_X],       dif(_X,a)                       ;
Ls = [a,a,_X,_Y],    dif(_X,a), dif(_Y,a)            ;
Ls = [a,a,_X,_Y,_Z], dif(_X,a), dif(_Y,a), dif(_Z,a) ...
于 2015-06-15T09:42:18.647 回答
2

@false 的解决方案尽可能干净。这是一个更详细的解决方案，用更简单的术语说明问题。要记住的一件事是，“重复”元素可能意味着一个元素恰好出现两次——这就是这个谓词解释它的方式——或者它可能意味着一个元素出现不止一次——这可能是你的意思（所以这个名字duplicate实际上是误导）

%% duplicate(List, Element) is true for every matching pair of _Element_ in _List_
duplicate([First|Rest], Element) :-
    duplicate_1(Rest, First, Element).

% First occurrence
duplicate_1([This|Rest], X, X) :- % first occurrence
    duplicate_2(Rest, This, X).
duplicate_1([This|Rest], _, X) :- % look further for first occurrence
    duplicate_1(Rest, This, X).

% Second occurrence
duplicate_2(_, X, X). % second occurrence
duplicate_2([This|Rest], _, X) :- % look further for second occurrence
    duplicate_2(Rest, This, X).

现在可以在各个方向使用：

?- duplicate([b,c,d,a,b,a,c], X).
X = b ;
X = c ;
X = a ;
false.

?- duplicate([b,c,d,a,b,a,c], a).
true ;
false.

?- duplicate(L, a).
L = [a, a|_G274] ;
L = [a, _G273, a|_G277] ;
L = [a, _G273, _G276, a|_G280] .

如果多个答案有问题，您将不得不使用削减、或dif/2、或once/1摆脱多个答案。具体如何取决于您要如何使用谓词。

于 2014-08-25T05:49:39.057 回答
0

对于您问题的第一部分，我找到了一个简单的解决方案：

duplicated([H|T], Item) :- H == Item, second_stage(T, Item).  %first occurence found
duplicated([H|T], Item) :- duplicated(T, Item).
second_stage([H|T], Item) :- H == Item.   %second occurence found -> match!
second_stage([H|T], Item) :- second_stage(T, Item).

这将给出带有重复（[1,2,3,1,5], 1）的真实 fe。

对于第二部分（使用变量查询），我将尝试找到一种方法……但我不知道这在 Prolog 中是否可行。

:)

于 2014-08-24T13:41:53.980 回答