Prolog中的子集

Question

Prolog中的子集

21

我正在寻找一个像这样工作的谓词：

?- subset([1,2,3], X).
X = [] ;
X = [1] ;
X = [2] ;
X = [3] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [2, 3] ;
...

我看到过一些subset的实现，但它们都是用于检查一个列表是否是另一个列表的子集，而不是用于生成子集。有什么办法吗？

- arubox

1

你应该交换 subset(X, Y) 谓词中的参数，这样我们自然地读作 X 是 Y 的子集，而不是像你所做的那样：Y 是 X 的子集。 - Dávid Natingga

5个回答

8

您可以在http://www.probp.com/publib/listut.html上找到一个名为subseq0的谓词实现，它可以完成您想要的功能：

subseq0(List, List).
subseq0(List, Rest) :-
   subseq1(List, Rest).

subseq1([_|Tail], Rest) :-
   subseq0(Tail, Rest).
subseq1([Head|Tail], [Head|Rest]) :-
   subseq1(Tail, Rest).

简要说明：subseq0(X, Y)检查Y是否是X的子序列，而subseq1(X, Y)则检查Y是否是X的真子序列。

由于集合的默认表示形式是一个具有唯一元素的列表，您可以使用它来获取所有子集，如以下示例所示：

?- subseq0([1,2,3], X).
X = [1, 2, 3] ;
X = [2, 3] ;
X = [3] ;
X = [] ;
X = [2] ;
X = [1, 3] ;
X = [1] ;
X = [1, 2] ;
false.

- Nubok

3

这会生成子序列，而不是子集。但是，当使用已排序的唯一元素列表时也是如此。 - Fred Foo

1

你基本上是正确的（已更正）。但是为什么你要求列表被排序呢？ - Nubok

你说得对，即使列表没有排序，只要使用 uniq 命令也能工作。但是获得唯一元素的最简单方法是通过 sort/2 命令 :) - Fred Foo

2

集合被定义为一组不同的对象。子集过程不应该关心集合中元素的顺序（在参数中）。一个正确的解决方案（SWI Prolog）可能是：

subset(_, []).
subset([X|L], [A|NTail]):-
    member(A,[X|L]),    
    subset(L, NTail),
    not(member(A, NTail)).

对于问题?- subset([1,2,3], E)，它将生成：

E = [] ;
E = [1] ;
E = [1, 2] ;
E = [1, 2, 3] ;
E = [1, 3] ;
E = [2] ;
E = [2, 3] ;
E = [3] ;
E = [3, 2] ;
false.

希望这能有所帮助！

- ostruk

1

subset([A,B],[C,D]). 失败了，但它应该成功才对。 - false

@false [C,D] 不是 [A,B] 的子集，它应该失败。 - Bao Thai

2

@BaoThai：它肯定是一个子集（其中答案替换为 A = C, B = D ; A = D，B = C）。 - false

1

@BaoThai：当 subset([A], [B]) 中的 A = B 时成功，但上述情况失败。 - false

1

@BaoThai：即使是subset([A,B],[A,B]).也失败了，我们至少可以认为这是错误的吗？ - false

1

我们还可以通过从超集中删除子集的项目来进行测试。

% to delete : an item can be deleted it its in the head or in the tail of a list
delete(I,[I|L],L).
delete(I,[H|L],[H|NL]) :- delete(I,L,NL).
% an [] is an item of an set.A set is a subset of we can recursively delete its head item from the super set.
subset(_,[]).
subset(S,[I|SS]) :- delete(I,S,S1), subset(S1,SS).

例子：

subset([a,b,c],S).
S = []
S = [a]
S = [a, b]
S = [a, b, c]
S = [a, c]
S = [a, c, b]
S = [b]
S = [b, a]
S = [b, a, c]
S = [b, c]
S = [b, c, a]
S = [c]
S = [c, a]
S = [c, a, b]
S = [c, b]
S = [c, b, a]

subset([a,b,a,d,e],[a,e]).
1true

- durga

这个解决方案返回了 [a, b] 和 [b, a] 两个结果，但实际上元素的顺序并不重要，只需要列出其中一个作为子集即可，因为它们代表同一个集合。 - Milos

-2

append([],L,L).

append([H|T],L,[H|L1]):-append(T,L,L1).


subset([X|T],[X|L]) :-subset(T,L).

subset([X|T],[G|L]) :-subset([X],L),append(L2,[X|L3],[G|L]),append(L2,L3,L4),subset(T,L4).

subset([],_).

----------------------------------------------
?- subset([1,2],[1,2]).

yes

?- subset([1,2],[2,1]).

yes

?- subset([1,1],[1,2]).

no

?- subset(D,[1,2]).

D = [1,2] ;

D = [1] ;

D = [2,1] ;

D = [2] ;

D = '[]' ;

no

- user3584276

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

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

- gusbro · Accepted Answer

这里是一个实现：

subset([], []).
subset([E|Tail], [E|NTail]):-
  subset(Tail, NTail).
subset([_|Tail], NTail):-
  subset(Tail, NTail).

它将生成所有子集，但不以你的示例顺序显示。

根据评论请求，以下是解释：

第一个子句是基本情况。它说明空列表是空列表的子集。

第二个和第三个子句涉及递归。第二个子句说明如果两个列表具有相同的头，并且右列表的尾部是左列表的尾部的子集，则右列表是左列表的子集。

第三个子句说明如果我们跳过左列表的头，右列表是左列表的尾部的子集，则右列表是左列表的子集。

上面显示的过程生成有序集。对于无序集，您可以使用permutation/3：

unordered_subset(Set, SubSet):-
  length(Set, LSet),
  between(0,LSet, LSubSet),
  length(NSubSet, LSubSet),
  permutation(SubSet, NSubSet),
  subset(Set, NSubSet).