0

我正在尝试创建 2 个列表的交集（即列表 C 包含那些且仅包含 A 和 B 中的那些元素），但据我所知，我得到了 2 个列表的析取 + C 中任意数量的任何元素。

打算像这样工作：

  • 如果 X 在 C 中，那么它必须同时在 A 和 B 中。（我相信 X 应该迭代 C 的所有成员！？）
  • 谓词：d(A,B,C) :- (member(X,D)->member(X,A),member(X,B)).

你能说：我的句子和谓词不相等还是我犯了另一个错误？

例子：

?- [user].

|: d(A,B,C) :- (member(X,D)->(member(X,A),member(X,B))).
|: % user://1 compiled 0.01 sec, 612 bytes
true.

?- d([a,b],[b,c],C)
|    .
C = [b|_G21] .

?- d([a,b],[b,c],[b]).
true .
4

3 回答 3

1

删除重复项的O(NlogN)解决方案：

% untested
intersection(A, B, O) :-
    sort(A, AS),
    sort(B, BS),
    intersection1(AS, BS, O).

intersection1(A, B, O) :-
    (    A = [AH|AT],
         B = [BH|BT]
    ->   (    AH == BH
         ->   O = [AH|OT],
              intersection1(AT, BT, OT)
         ;    (    AH @< BH
              ->   intersection1(AT, B, O)
              ;    intersection1(A, BT, O) ) )
     ;   O = [] ).
于 2013-11-06T15:32:21.867 回答
1

我喜欢@salva 提出的解决方案，尽管我会做一个更直接的排序和合并，而是丢弃任何不匹配的东西：

intersect( As , Bs , Cs ) :-
  sort( As , SortedAs ) ,
  sort( Bs , SortedBs ) ,
  merge( SortedAs , SortedBs , Cs )
  .

merge( []     , []     , [] ).
merge( []     , [_|_]  , [] ).
merge( [_|_]  , []     , [] ).
merge( [C|As] , [C|Bs] , [C|Cs] ) :-          merge(    As ,     Bs  , Cs ) .
merge( [A|As] , [B|Bs] , Cs     ) :- A @< B , merge(    As  , [B|Bs] , Cs ) .
merge( [A|As] , [B|Bs] , Cs     ) :- A @> B , merge( [A|As] ,    Bs  , Cs ) .
于 2013-11-06T18:56:06.413 回答
0

您的谓词 d/3 应该以建设性的方式重新表述，因为 Prolog 它是“一次元组”关系语言：

d(X,Y,Z) :- findall(E, (member(E,X), memberchk(E,Y)), Z).

产生

?- d([a,b],[b,c],C).
C = [b].

memberchk /2 它是member /2的确定性版本，用于枚举所有 X' 元素。如果您将 memberchk 替换为 member 并尝试使用包含重复项的列表调用 d/3，您可以更好地理解差异。

findall /3 它是更简单的“所有解决方案”列表构造函数。

于 2013-11-06T15:42:36.263 回答