Instantly share code, notes, and snippets.

# AndrewBrinker/powerset.plSecret Created Nov 28, 2017

 % Credit to Rosetta Code [1], with modifications % % [1]: https://rosettacode.org/wiki/Power_set#Prolog % Here, X is the thing we want the powerset of, and Y will contain % the powerset. % % We are defining the powerset as being a "bag" of all subsequences `S` % (there is already a Prolog function called `subset`) of the set `X`, % with the results collected into `Y`. powerset(X,Y) :- bagof(S, subseq(S,X), Y). % This says that the empty list is a subsequence of itself, and that the empty % list is a subsequence of any list with a head and a tail (the `[_|_]` notation), % together, these make sure the empty list is given as a subsequence of all lists. % % Then is says that a subsequence of a list is defined as containing the first % element of the list, plus a subsquence of the rest. % % Finally, it says a subsequence is some element in any position of the original % list, plus a subsequence of the rest of the list. % % Notice that collectively, this doesn't say how to find those subsequences, it % says what a subsequence _is_. Prolog then searches for subsequences using these % rules. % % Also note that Prolog would usually stop after finding one subsequence, but that % `bagof` makes it keep going until all the subsequences have been found. subseq([], []). subseq([], [_|_]). subseq([X|Xs], [X|Ys] ) :- subseq(Xs, Ys). subseq([X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs).