logo标签列表

集合的相等性

prolog
6

有人能帮我完成以下任务吗：我需要定义一个谓词eq_set，当集合S1和S2在元素数量方面相等时，它就会成功。

但是它只适用于完全相同的数目和顺序。我想创建一段代码，展示所有变体并且不考虑顺序。请帮帮我好吗？

我写道：

eq_set([],[]).
eq_set([H|T],[H|T1]) :-
    eq_set(T,T1).

但是它只在数字完全相同且顺序一致时有效。我想创建一个代码，显示所有的变化并且不考虑顺序。

我对这个作业的最接近翻译是：“定义谓词eq_set，如果集合（S1，S2）重合，则成功。”

谢谢，这解决了问题的一部分。当我进行了更正后，它显示 [1,2,3] 等于 [4,5,6] ，这意味着仅考虑长度。建议我使用谓词“member”和“subset”来尝试定义 S1 的元素应该是 S2 中的元素。这意味着，例如，[1,2,3] 应该被认为等于 [3,2,1]，现在确实如此，但它应该能够比较元素...如果您能帮助我，我将非常感激，并且对自己有点迟钝深感抱歉。 - Pressy Lazarova
两个集合在它们具有完全相同的元素时重合，对吗？只是要明确一下。这些集合被表示为无序且没有重复项的列表，是吗？（不是绝对确定，这有点重要）。这两个参数中必须至少有一个是ground吗？Nonvar？请给出在toplevel上查询谓词的示例。 - User9213
你能给出这个任务的保加利亚语版本吗？ - Borislav Stoilov
4个回答
2
你称它们为“集合”，但你使用的数据结构是列表。最简单的方法是对这两个列表进行排序： "sets"实际上指的是集合，但你使用的数据结构是列表。最好的方法是将这两个列表排序：
eq_set(A, B) :-
    % prerequisites: A and B are lists without duplicates
    sort(A, S),
    sort(B, S).

如果您需要更复杂的东西（由于某种原因），您需要更具体地说明。
有了这个定义：

Original Answer:

最初的回答：
?- eq_set([a,b,c], [a,b]).
false. % OK

?- eq_set([a,b,c], [a,b,c]).
true. % OK

?- eq_set([a,c,b], [a,b,c]).
true. % OK

?- eq_set([a,a,b], [a,b,b]).
true. % Not sure....
他们告诉我它们不应该是列表。这是一个任务，应该很简单，但对我来说很困难，因为我是一名语言学家，我的术语可能不是最好的。我被建议使用谓词“成员”和/或“子集”，我认为这应该能够给我其他可能的选项（[1,2,3]，[3,2,1]，[2,3,1]等等）。我没有准备数据库，也不认为我应该准备。它必须在对话中起作用。 - Pressy Lazarova
@PressyLazarova，您真的需要详细描述您的任务和上下文。 "他们"是谁？ [1, 2, 3] _是一个列表_，所以为什么“他们”会告诉您这样的事情？如果您是语言学家，您必须知道如何使用术语（我认识一些语言学家，他们显然不是“有点迟钝”）。 - User9213
嗯，对我来说很难用正确的英语术语详细描述它，因为任务是用保加利亚语给我的。 “他们”是给我分配任务并建议我使用“成员”谓词的老师。 我会尽力翻译任务：“定义谓词eq_set，如果集合（S1，S2）相同，则成功。我知道其他类型的术语，这是我第一次遇到任何类型的编程，所以不要太苛刻 :) - Pressy Lazarova
@PressyLazarova 好的，接近了。还有两个问题：a）_如何表示_“集合”？（似乎是一个没有重复项的_Prolog列表_，但不按任何特定顺序排列，并且我猜“相符”意味着如果您对元素进行排序，则两个列表将相同？）；b）您应该如何使用谓词？第二个问题可能比较难回答，需要更多上下文。至少给出几个示例。像这样是否有效：?- eq_set([a,b] S). S = [a, b] ; S = [b,a]. - User9213
问题如下：如果您有一个谓词，用于测试没有重复项的两个列表中是否存在相同元素集，则按我所示的方式进行排序是最佳方法。但是，如果您想要将其作为一般关系来处理，那么我们需要深入细节，例如“如何表示集合”，“在此表示中两个集合何时相同”，“谓词的参数可以是非地面或甚至自由变量”等等。 - User9213
显示剩余2条评论
2
“这真的取决于谓词将如何使用。”
“假设‘set’确实是一个没有重复但没有特定顺序的Prolog列表；那么在该表示中，如果两个集合是彼此的排列，则它们“重合”。换句话说，只需将‘eq_set/2’定义为：”
eq_set(A, B) :-
    my_permutation(A, B).

"只需使用教科书中对于 'permutation/2' 的定义，该定义使用了 'select/3' 的教科书定义（参见 Sterling 和 Shapiro 的《Prolog 艺术（第二版）》，第 67-9 页）："
my_permutation([], []).
my_permutation(Xs, [Y|Ys]) :-
    my_select(Y, Xs, Xs0),
    my_permutation(Xs0, Ys).

my_select(X, [X|Xs], Xs).
my_select(X, [Y|Ys], [Y|Zs]) :-
    my_select(X, Ys, Zs).

我将它们重命名，以确保我没有使用标准库定义； SWI-Prolog在{{link3：autoloaded library（lists）}}中同时有{{link1：select / 3 }}和{{link2：permutation / 2 }}; 它们的定义基本相同，但对参数进行了一些运行时类型检查。
下面是如何使用它们：
?- eq_set([1,2,3], [2,3,1]).
true ;
false.

?- eq_set([1,2,3], S).
S = [1, 2, 3] ;
S = [1, 3, 2] ;
S = [2, 1, 3] ;
S = [2, 3, 1] ;
S = [3, 1, 2] ;
S = [3, 2, 1] ;
false.

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

?- eq_set(A, B).
A = B, B = [] ;
A = B, B = [_4480] ;
A = B, B = [_4480, _4492] ;
...

我不确定最后一个查询有多大用处。你可以强制它按“集合”的大小递增的顺序枚举解决方案，像这样：
?- length(S1, _), eq_set(S1, S2), numbervars(S1).
S1 = S2, S2 = [] ;
S1 = S2, S2 = [A] ;
S1 = S2, S2 = [A, B] ;
S1 = [A, B],
S2 = [B, A] ;
S1 = S2, S2 = [A, B, C] ;
S1 = [A, B, C],
S2 = [A, C, B] ;
S1 = [A, B, C],
S2 = [B, A, C] ;
S1 = [A, B, C],
S2 = [B, C, A] ;
S1 = [A, B, C],
S2 = [C, A, B] ;
S1 = [A, B, C],
S2 = [C, B, A] ;
S1 = S2, S2 = [A, B, C, D] .

“不用担心`numbervars`，它只是为集合中的所有自由变量提供可读的名称。请记住，将两个自由变量统一起来会使它们成为同一个变量。”
“这是一个起点，但也许已经足够好了。最明显的遗漏是它没有要求参数是不含重复项的列表。定义这个的一种方法是要求每个元素与所有其他元素都不相同。由于“不同”是可交换的，因此可以像这样定义它：”
is_set([]).
is_set([X|Xs]) :-
    all_different(Xs, X),
    is_set(Xs).

all_different([], _).
all_different([Y|Ys], X) :-
    dif(X, Y),
    all_different(Ys, X).

这里使用了 dif/2，它是一个广泛可用的谓词（但你的 Prolog 是否有它还需确认）。
对于最后一个例子，我们可能会使用 maplist：
is_set([]).
is_set([X|Xs]) :-
    maplist(dif(X), Xs).
    is_set(Xs).
1
你的解决方案已经很接近了。
我们有两种情况： 1）第一个列表参数更大 2）第二个列表参数更大
如果你已经知道哪一个更大，可以直接执行。
%in case the left one is longer
eq_set_left(_,[]).
eq_set_left(X,[H|T]):-member(H,X), eq_set_left(X,T).

因此，一个非常简单但又非常优化的解决方案可能是这样的：

%in case the right one is longer
eq_set_right([],_).
eq_set_right([H|T], X):- member(H,X), eq_set_right(T,X).

%in case the left one is longer
eq_set_left(_,[]).
eq_set_left(X,[H|T]):-member(H,X), eq_set_left(X,T).

%both cases, equal length is also included here
eq_set(X,Y):- eq_set_left(X,Y).
eq_set(X,Y):- eq_set_right(X,Y).

如果X是Y的子集，Y是X的子集或它们相等，则eq_set（X，Y）为真

无论如何都只会输出“false”：`? - eq_set（[1]，[1]）。 false。？- eq_set_left（[1]，[1]）。 false。？- eq_set_right（[1]，[1]）。 false。我认为您错误地使用了 member/2。抱歉，在至少修改这个问题之前，我要投反对票。 - User9213
但是你是如何得出实际语义的呢？比如现在，它说，“如果X是Y的子集，Y是X的子集或它们相等，则eq_set（X，Y）为真”。这与原始问题中的“两个集合重合”有什么关系？我之所以问是因为这正是我无法从OP那里获取的缺失信息。 - User9213
你的解决方案还存在其他小问题，但首先我想了解这个问题。 - User9213
我对问题的理解是： 我们有两个集合A和B。 如果A的所有元素都包含在B中，或者B的所有元素都包含在A中，则eq_set应为true。 - Borislav Stoilov
在更传统的用法中，“两个集合重合”是指两个集合具有相同的元素，也就是说，这两个集合实际上是相等的。（取消了踩，因为代码确实实现了它所声称的功能。不确定它是否回答了问题）。 - User9213
显示剩余2条评论
0

集合被定义为一组不同的事物的集合，其中顺序不重要，也就是说，集合{a,b,c}和{b,a,c}是相同的。

由此可见，如果两个集合都不包含另一个集合中没有的元素，则可以说它们是相同的（或者反过来，如果任何一个集合包含另一个集合中没有的元素，则这两个集合不相同）。

由此，我们可以简单地说：

eq_set(Xs,Ys) :-
   findall( (Xs,Ys) , ( member(X,Xs), \+ member(X,Ys) ), [] ),
   findall( (Xs,Ys) , ( member(Y,Ys), \+ member(Y,Xs) ), [] )
   .

或者如果您不想使用内置的findall/3，

eq_set(Xs,Ys) :-
  a_not_in_b( Xs , Ys , [] ) ,
  a_not_in_b( Ys , Xs , [] ) .

a_not_in_b( []     , [] , [] ) .
a_not_in_b( [A|As] , Bs , Xs ) :- member(A,Bs) , a_not_in_b( As, Bs,    Xs  ) .
a_not_in_b( [A|As] , Bs , Xs ) :-                a_not_in_b( As, Bs, [A|Xs] ) .

需要注意的是，这两种方法的性能大致为O(N2)。如果所涉及的集合很大，您可能希望先对每个集合进行排序，然后合并两个已排序的列表以识别那些不共同存在于两个集合中的元素。
eq_set(Xs,Ys) :-
  sort(Xs,X1),
  sort(Ys,Y1),
  X1 == Y1.
这个问题并不是很清楚，但似乎查询 ?- eq_set([a, b], S). 应该回答 S = [a, b] ; S = [b, a]。在你的回答中，解决方案1和2没有终止，解决方案3会抛出实例化错误。解决方案3也只是此答案的一个不必要冗长的版本。如果我不知道得更好，我几乎会说你没有阅读问题或现有的答案 :-( - User9213
PS：sort/2的第二个参数是有限列表。对于两个这样的列表，只有当列表具有自由变量时，A == B和A = B才不同，而我正在努力找出在eq_set/2的上下文中不统一它们的用途。 - User9213
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接