list Prolog 中的子集
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4912869/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Subsets in Prolog
提问by arubox
I'm looking for a predicate that works as this:
我正在寻找一个这样的谓词：
?- subset([1,2,3], X).
X = [] ;
X = [1] ;
X = [2] ;
X = [3] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [2, 3] ;
...
I've seen some subsetimplementations, but they all work when you want to check if one list is a subset of the another, not when you want to generate the subsets. Any ideas?
我见过一些subset实现，但是当您想检查一个列表是否是另一个列表的子集时，它们都可以工作，而不是当您想要生成子集时。有任何想法吗？
回答by gusbro
Here goes an implementation:
这是一个实现：
subset([], []).
subset([E|Tail], [E|NTail]):-
subset(Tail, NTail).
subset([_|Tail], NTail):-
subset(Tail, NTail).
It will generate all the subsets, though not in the order shown on your example.
它将生成所有子集，尽管不是按照示例中显示的顺序。
As per commenter request here goes an explanation:
根据评论者的要求，这里有一个解释：
The first clause is the base case. It states that the empty list is a subset of the empty list.
第一个子句是基本情况。它指出空列表是空列表的子集。
The second and third clauses deal with recursion. The second clause states that if two lists have the same Head and the tail of the right list is a subset of the tail of the left list, then the right list is a subset of the left list.
第二个和第三个子句处理递归。第二个子句指出，如果两个列表具有相同的 Head 并且右列表的尾部是左列表尾部的子集，则右列表是左列表的子集。
The third clause states that if we skip the head of the left list, and the right list is a subset of the tail of the left list, then the right list is a subset of the left list.
第三个子句说明，如果我们跳过左表的头部，而右表是左表尾部的子集，那么右表是左表的子集。
The procedure shown above generates ordered sets. For unordered sets you might use permutation/3:
上面显示的过程生成有序集。对于无序集合，您可能会使用permutation/3：
unordered_subset(Set, SubSet):-
length(Set, LSet),
between(0,LSet, LSubSet),
length(NSubSet, LSubSet),
permutation(SubSet, NSubSet),
subset(Set, NSubSet).
回答by Nubok
On http://www.probp.com/publib/listut.htmlyou will find an implementation of a predicate called subseq0that does what you want to:
在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).
A short explanation: subseq0(X, Y)checks whether Y is a subsetsubsequence of X, while subseq1(X, Y)checks whether Y is a propersubsetsubsequence of X.
一个小解释：subseq0(X, Y)检查y是否一个子集X的序列，而subseq1(X, Y)检查是否Y为适当的子集X的子序列
Since the default representation of a set is a list with unique elements, you can use it to get all subsets as in the following example:
由于集合的默认表示是具有唯一元素的列表，因此您可以使用它来获取所有子集，如下例所示：
?- 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.
回答by Volodymyr Ostruk
Set is a collection of distinctobjects by definition. A subset procedure shouldn't careabout the order of elements in the set(in the arguments). A proper solution(swi prolog) may look like:
根据定义，集合是不同对象的集合。子集过程不应该关心集合中元素的顺序（在参数中）。正确的解决方案（swi prolog）可能如下所示：
subset(_, []).
subset([X|L], [A|NTail]):-
member(A,[X|L]),
subset(L, NTail),
not(member(A, NTail)).
For the question ?- subset([1,2,3], E) it will generate:
对于问题 ?-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.
Hope it will help!
希望它会有所帮助！
回答by durga
we can also test by deleting subset's item from the super set.
我们也可以通过从超集中删除子集的项目来进行测试。
% 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).
example:
例子：
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
回答by durga
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
