0

我正在尝试在 Prolog 中编写联合函数，但遇到了一些麻烦。我已经查找了示例并列出了联合的内置示例，但我正在为作业编写自己的示例。当列表具有重复值和/或列表的顺序不是升序时，我注意到一些奇怪的结果。以下是内置的联合代码：

union([], A, A) :- !.
union([A|C], B, D) :-
        memberchk(A, B), !,
        union(C, B, D).
union([A|B], C, [A|D]) :-
        union(B, C, D).

我相信这里的伪代码是我们希望在结果中找到所有列表 1，一旦用尽，我们比较列表 2 和列表 3。它们应该是相同的。但是，这不会检查订单。

30 ?- union([1,2,3],[],[3,2,1]).
false.

为什么这是假的？清单 1 和清单 3 是相同的集合，即使顺序不同！

24 ?- union([a],[a,a],[a,a]).
true.

25 ?- union([a,a],[a],[a,a]).
false.

这两者有什么不同？它们应该产生相同的结果。但是，由于函数的编写方式，最后我们只比较了列表 2 和列表 3，它们在第 25 行是不同的。

我的问题是。. . 有没有更好的方法来编写这些函数，以便正确处理重复项并且顺序无关紧要？有人会假设内置方法可以解决问题，但没有骰子。

4

3 回答 3

1

First, it's easier to read a code written with consistent naming:

union([], A, A) :- !.
union([A|B], C, D) :-
        memberchk(A, B), !,
        union(B, C, D).
union([A|B], C, [A|D]) :-
        union(B, C, D).

What does it do? Given two lists A and B, it produces the result with a prefix of all elements of A not present in B, and then B itself. So, union([1,2,3],[],[1,2,3]). And also union([1,2,3],[2],[1,3,2]). You see that order is preserved here. So if you want to compare lists regardless of their order, you should write a special, additional predicate for that: union([1,2,3],[],X), regardless(X,[3,2,1]) should work then.

Same with the duplicates - your set equality predicate should disregard any. union as presented above OTOH is not about sets, but about lists. There are many different lists representing the same set, but as lists they are considered different.

In your 25 you hit the issue of duplicates: union([a,a],[a],X) produces X=[a]. Again, as set it is the same as [a,a], but as lists they are different.

One strategy for coping with this is to represent sets as strictly increasing lists - if your elements have order well defined for them. Then we can write union such that given two sets according to that definition, it will also produce a set, and it will work efficiently at that:

union([],X,X):-!.
union(X,[],X):-!.
union([A|B],[C|D],[H|T]):-
  A @< C -> H=A, union(B,[C|D],T) ;
  C @< A -> H=C, union([A|B],D,T) ;
  H=A, union(B,D,T).

We will have to define make_set/2 predicate here too. Even better (in some respects) is representing sets (again, of comparable elements) by self-balancing binary trees.

于 2013-01-28T10:57:54.873 回答
0

您正在使用语言（Prolog，在您的情况下）放在您手中的“工具”来实现一个概念。那么你应该更好地定义（首先用自然语言）你的目标是什么，考虑到append /3 也可以符合联合概念。

如果...，您可以将列表C称为列表A，B之间的并集。

我会这样填写省略号

  • 每个 A 元素在 C 中出现一次，并且
  • 每个 B 元素在 C 中出现一次，并且
  • 每个 C 元素出现在 A或B

如果你同意这个定义，那么一个实现可能是

union(A, B, C) :-
  elems_once(A, [], C1),
  elems_once(A, C1, C2),
  each_elems(C2, A, B, C).

这比显示的库代码效率低得多，但这是一般性的代价......

于 2013-01-28T11:02:05.527 回答
0

为了有一个union(?A, ?B, ?C)（也就是说，你可以使用任何变量作为输入或输出）我创建了一个新的联合

uniao(?A, ?B, ?C)

list:union除其他外使用，如：

uniao([], [], []) :- !.

uniao(X, [], X) :- !.

uniao([], X, X) :- !.

uniao(X, Y, Z) :-
    nonvar(X),
    nonvar(Y),
    var(Z),
    list_to_set(X, Xs),
    list_to_set(Y, Ys),
    union(Xs, Ys, Z), 
    !.  

uniao(X, Y, Z) :-
    nonvar(X),
    var(Y),
    nonvar(Z),
    list_to_set(X, Xs),
    list_to_set(Z, Zs),
    subset(Xs, Zs),
    subtract(Zs, Xs, Y), 
    !.  

uniao(X, Y, Z) :-
    var(X),
    nonvar(Y),
    nonvar(Z),
    list_to_set(Y, Ys),
    list_to_set(Z, Zs),
    subset(Ys, Zs),
    subtract(Zs, Ys, X),
    !.

uniao(X, Y, Z) :-
    nonvar(X),
    nonvar(Y),
    nonvar(Z),
    list_to_set(X, Xs),
    list_to_set(Y, Ys),
    list_to_set(Z, Zs),
    union(Xs, Ys, Ts),
    subtract(Zs, Ts, []),
    subtract(Ts, Zs, []),
    !.
于 2015-12-15T16:04:29.997 回答