Prolog :执行两个数组的交集，不使用内置函数(如交集，成员)

Question

我已经使用prolog中的交集执行了两个数组的交集。我怎么才能在不使用“交集”的情况下手动执行这个任务呢？

intersection([],[],[]).
intersection(_,[], []).
intersection(List1, [Head2|Tail2], output):-
    \+(member(Head2, List1)), intersection(List1, Tail2, output).
intersection(List1, [Head2|Tail2], [Head2|output]):-
    member(Head2, List1), intersection(List1, Tail2, output).

Answer 1

事实上，根据所使用的编译器，可以创建比预定义谓词intersection/3更高效的谓词来计算集合交集。在SWI-Prolog 8.2.1版本中，我获得了以下结果：

intersection1(A, B, I) :-
    setup_call_cleanup(
        dynamic('$elem'/1),
        ( maplist([X] >> assertz('$elem'(X)), A),
          convlist([X,X] >> retract('$elem'(X)), B, I)),
        abolish('$elem'/1)).

intersection2(A, B, I) :-
    setup_call_cleanup(
        dynamic('$elem'/1),
        ( forall(member(X,A), assertz('$elem'(X))),
          findall(X, (member(X,B), retract('$elem'(X))), I)),
        abolish('$elem'/1)).

test_intersection(N) :-
    M is 10*N,
    randseq(N, M, A),
    randseq(N, M, B),
    time(intersection( A, B, I0)),
    time(intersection1(A, B, I1)),
    time(intersection2(A, B, I2)),
    sort(I0, S),
    sort(I1, S),
    sort(I2, S).

一些测试：

?- intersection([1,3,4,7,8,9], [0,2,3,4,6,9], I).
I = [3, 4, 9].

?- intersection1([1,3,4,7,8,9], [0,2,3,4,6,9], I).
I = [3, 4, 9].

?- intersection2([1,3,4,7,8,9], [0,2,3,4,6,9], I).
I = [3, 4, 9].

较大集合的执行时间：

?- test_intersection(10000).
% 20,992 inferences, 2.875 CPU in 2.875 seconds (100% CPU, 7302 Lips)
% 70,013 inferences, 0.016 CPU in 0.016 seconds (100% CPU, 4480832 Lips)
% 41,014 inferences, 0.016 CPU in 0.016 seconds (100% CPU, 2624896 Lips)
true.

?- test_intersection(20000).
% 42,053 inferences, 11.203 CPU in 11.196 seconds (100% CPU, 3754 Lips)
% 140,013 inferences, 0.031 CPU in 0.031 seconds (100% CPU, 4480416 Lips)
% 82,075 inferences, 0.031 CPU in 0.031 seconds (100% CPU, 2626400 Lips)
true.

?- test_intersection(40000).
% 83,948 inferences, 47.563 CPU in 47.645 seconds (100% CPU, 1765 Lips)
% 280,013 inferences, 0.078 CPU in 0.070 seconds (112% CPU, 3584166 Lips)
% 163,970 inferences, 0.078 CPU in 0.078 seconds (100% CPU, 2098816 Lips)
true.

我们可以看到，当集合的大小翻倍时，intersection1/3和intersection2/3的执行时间也几乎翻了一番，即时间复杂度为O(n)，而预定义谓词intersection/3的执行时间约为4倍，即时间复杂度为O(n^2)。

当然，如前所述，这将取决于所使用的编译器。

Answer 2

以下是我的方法：

其思想是将一个列表中的每个元素与另一个列表中的每个元素进行比较。如果H1=H2，那么我们有一个交集，否则，我们没有。所以，当交集找到时，把它放到新的列表中，否则，不要。我们使用flatten去掉空方括号，返回最终的答案。

intersection([H|T],[H2|T2],List):-
    intersection1([H|T],[H2|T2],R),
    flatten(R,List).

intersection1([],_,[]).
intersection1([H|T],[H2|T2],[R|List]):-
    intersection2(H,[H2|T2],R),
    intersection1(T,[H2|T2],List).

intersection2(_,[],[]).
intersection2(H1,[H2|T2],[H1|L]):-
    H1=H2,
    intersection2(H1,T2,L).
intersection2(H1,[H2|T2],L):-
    H1\=H2,
    intersection2(H1,T2,L).

示例：

?-intersection([12, 3, 9,4,1],[6,7,4,8],List).
List = [4]

?-intersection([6,4,8,2],[6,7,4,8],List).
List = [6, 4, 8]

?-intersection([12,6,4],[5,2,1],List).
List = []

?-intersection([12,6,4,7,88],[88,5,7,2,1],List).
List = [7, 88]