Power set: Difference between revisions
Content deleted Content added
→Python: Standard documentation: Added. |
Logical (cut-free) Definition |
||
| Line 1,705: | Line 1,705: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
===Logical (cut-free) Definition=== |
|||
The predicate powerset(X,Y) defined here can be read as "Y is the |
|||
powerset of X", it being understood that lists are used to represent sets. |
|||
The predicate subseq(X,Y) is true if and only if the list X is a subsequence of the list Y. |
|||
The specifications here are elementary, logical (cut-free), and efficient. |
|||
<lang Prolog> |
|||
powerset(X,Y) :- bagof( S, subseq(S,X), Y). |
|||
/* subseq(X,Y) will only be true if the list X is a subsequence of the list Y */ |
|||
subseq( [], []). |
|||
subseq( [], [_|_]). |
|||
subseq( [X|Xs], [X|Ys] ) :- subseq(Xs, Ys). |
|||
subseq( [X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs). |
|||
</lang> |
|||
Output : |
|||
<pre> |
|||
?- powerset([1,2,3], X). |
|||
X = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]. |
|||
</pre> |
|||
===Single-Functor Definition=== |
|||
<lang Prolog>power_set(T, PS) :- |
<lang Prolog>power_set(T, PS) :- |
||
bagof(PS1, power_set(T, [], PS1), PS). |
bagof(PS1, power_set(T, [], PS1), PS). |
||
| Line 1,716: | Line 1,741: | ||
</lang> |
</lang> |
||
Output : |
Output : |
||
<pre> |
<pre> ?- power_set([1,2,3,4], L). |
||
L = [[1],[2],[3],[4],[],[3,4],[2,3],[2,4],[2,3,4],[1,2],[1,3],[1,4],[1,3,4],[1,2,3],[1,2,4],[1,2,3,4]]. |
L = [[1],[2],[3],[4],[],[3,4],[2,3],[2,4],[2,3,4],[1,2],[1,3],[1,4],[1,3,4],[1,2,3],[1,2,4],[1,2,3,4]]. |
||
</pre> |
</pre> |
||