在列表中查找唯一项

Question

在列表中查找唯一项

3

我正在尝试编写一条规则，以确定一个项目 X 是否恰好在列表 L 中出现一次。

unique(X, [X|T]):- !, \+ member(X, T).
unique(X, [_|T]):- unique(X, T).

该规则用于确定列表中的值是否唯一，但是当我尝试使用unique(X, [1,2,3,1,3,2,5,4,3,8]).来获取列表中的唯一值时，它仅返回false. 我期望的结果是这样的（类似于member(X, list).）：

X = 5 ;
X = 4 ;
X = 8 ;

我是一个完全的初学者，不知道我做错了什么。

- Bora M. Alper

发现了这个：http://computer-programming-forum.com/55-prolog/d2b17b566dad6b41.htm - Bora M. Alper

4个回答

5

这里有一个简单的解决方案，使用nth0/4（或者像@false指出的那样使用select/3）：

unique(X, L) :-
    nth0(_, L, X, R),
    \+ member(X, R).

nth0/4函数中的第四个参数R是列表L中移除元素X后的结果。我们只需要检查X是否不在R中即可。

更好的版本

unique(X, L) :-
    nth0(_, L, X, R),
    maplist(dif(X), R).

这修复了@false指出的问题，但由于您是初学者，我怀疑这对您并没有太大的兴趣。

这样做的好处在于它适用于像这种情况:

?- unique(b, [X, Y, a]).
X = b,
dif(Y, b) ;
Y = b,
dif(X, b) ;
false.

- Fatalize

2

@false 已添加了一个改进版。 - Fatalize

2

你的第二个版本非常好，因为它只是重用了现有的递归谓词，但它本身并不是递归的。然而，这种优雅的方式是需要付出代价的（程序上）。unique(a,[a,a|_]) 无法终止。 - false

1

@false 如果 L 没有足够的地面，它会出现问题。尽管这个版本适用于可接受的情况子集，但您的版本是更好的实现，对于初学者来说更易读。 - Fatalize

2

小注：select(X, L, R) 更为常见（我完全不知道 nth0/4）。 - false

0

这听起来像是一个作业问题。

试试这个。

unique(M, L) :- member(M, L), count(M, L, 1).  
count(M, [H|T], C) :- M = H, count(M, T, C1), C is C + 1.
...

完成后，这将会给出...

?- unique(X, [1,2,3,1,3,2,5,4,3,8]).
X = 5 ;
X = 4 ;
X = 8 ;
false.

编辑：既然已经有答案了...这是一个简洁的方法。

unique(Item, List) :-
  select(Item, List, L2),
  \+ member(Item, L2).

- ian_andrcih

0

简单纯粹的方法：

unique_elem_in_list(Elem, Lst) :-
    select(Elem, Lst, Rem),
    maplist(dif(Elem), Rem).

在swi-prolog中的结果：

?- unique_elem_in_list(E, [A,B,C]).
E = A,
dif(A, B),
dif(A, C) ;
E = B,
dif(B, A),
dif(B, C) ;
E = C,
dif(C, A),
dif(C, B).

- brebs

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- false · Accepted Answer

你一直在使用剪切和不安全的否定形式。两者都必须小心使用。一个即时的修复方法是保护你的程序免受未设计的用途：

unique(X, Xs) :-
   when_si(ground(X+Xs), your_unique(X, Xs)).

这使用when_si/2（之前称为iwhen/2），类似于when/2，但它不延迟：

:- meta_predicate(when_si(+, 0)).

when_si(Cond, G_0) :-
   when(Cond, ( Called = true, G_0 ) ),
   ( var(Called) -> throw(error(instantiation_error,_)) ; true ).

上述工作适用于提供when/2的系统。以下适用于任何符合ISO标准的系统：

when_si(Cond, G_0) :-
   (  when_condition(Cond)
   -> ( Cond -> G_0 ; throw(error(instantiation_error,_)) )
   ;  throw(error(domain_error(when_condition, Cond),_))
   ).

when_condition(C) :-
   var(C),
   !,
   throw(error(instantiation_error,_)).
when_condition(ground(_)).
when_condition(nonvar(_)).
when_condition(?=(_, _)).
when_condition(( A, B )) :-
   when_condition(A),
   when_condition(B).
when_condition(( A ; B )) :-
   when_condition(A),
   when_condition(B).

另一方面，每次都收到实例化错误而不是真正的答案，这真的很令人沮丧。所以，让我们让你的程序真正纯净起来！

你的第二个规则

unique(X, [_|Es]) :-
   unique(X, Es).

以声明方式从右到左阅读（即:-是←）

假设X是列表Es的唯一元素，则X也是列表[_|Es]的唯一元素。

换句话说：只要我知道X在Es中是唯一的，它也将与Es中的任何其他元素一起是唯一的。但这个结论并不正确，考虑通过添加X来扩展列表！您需要一些额外的条件。另外，您的第一个规则需要重新表述。这使用了non_member/2。

unique(X, [X|Es]) :-
   non_member(X, Es).
unique(X, [E|Es]) :-
   dif(X, E),
   unique(X, Es).

这里是另一种使用 tfilter/3 的方法：

unique(X, Es) :-
   tfilter(=(X), Es, [_]).

最高效的可能是以下使用if_/3的library(reif)：

unique(X, [E|Es]) :-
   if_(X = E, non_member(E, Es), unique(X, Es) ).