Question

Sets can be though of as lists that don't contain any repeated elements. For example, [a,4,6] is a set, but [a,4,6,a] is not (as it contains 2 occurrences of a). Write a Prolog program, powerset/2 that generates the set of all subsets of a list in sorted order. (Note the input list may not, itself, be a set.) Example1: powerset([a,b],X). should yield: X = [[],[a],[a,b],[b],[b,a]]. Example2: powerset([a,b,a],X). should also yield (note input list is not actually a set): X = [[],[a],[a,b],[b],[b,a]]. Example3: powerset([a,b,a,c],X). should yield: X = [[], [a], [a, b], [a, b, c], [a, c], [a, c, b], [b], [b, a], [b, a, c], [b, c], [b, c, a], [c], [c, a], [c, a, b], [c, b], [c, b, a]]. Also, the predicate should terminate execution immediately after producing its first (and only) solution.

Answer 1

%% ?- subset([a,b],[a,b,c])
	%% yes
	%% ?- subset([c,b],[a,b,c])
	%% yes
	%% ?- subset([],[a,b,c])
	%% yes
	%% Your program should be capable of generating all subsets of an input set by
	%% backtracking. For example, if you give it as input
	%% ?- subset(X,[a,b,c])
	%% it should successively generate all eight subsets of [a,b,c].
	%% Generates all subsets of the given set (once each)
	%% base case
	subset_gen([], []).
	%% inductive case
	subset_gen(Subset, [H | Set]) :- subset_gen(Subset, Set).
	subset_gen([H |Subset], [H | Set]) :- subset_gen(Subset, Set).
	%% Checks if the first argument is a subset of the second
	%% base case
	subset_check([], _).
	%% inductive case
	subset_check([H | Subset], Set) :-
	member(H, Set),
	subset_check(Subset, Set).
	%% main
	subset(Subset, Set) :-
	var(Subset),
	subset_gen(Subset, Set).
	subset(Subset, Set) :-
	nonvar(Subset),
	subset_check(Subset, Set).
	%% 2. Using the subset predicate you have just written, and findall/3 , write a
	%% predicate powerset/2 that takes a set as its first argument, and returns the
	%% powerset of this set as the second argument. (The powerset of a set is the
	%% set of all its subsets.) For example:
	%% ?- powerset([a,b,c],P)
	%% should return
	%% P = [[],[a],[b],[c],[a,b],[a,c],[b,c],[a,b,c]]
	%% It doesn’t matter if the sets are returned in some other order. For example,
	%% P = [[a],[b],[c],[a,b,c],[],[a,b],[a,c],[b,c]]
	%% is fine too
	%% main
	powerset(Set, Powerset) :- setof(Subset, subset(Subset, Set), Powerset).