/*
Power set (Rosetta Code) in Picat.
http://rosettacode.org/wiki/Power_set
"""
A set is a collection (container) of certain values, without
any particular order, and no repeated values. It corresponds
with a finite set in mathematics. A set can be implemented
as an associative array (partial mapping) in which the value
of each key-value pair is ignored.
Given a set S, the power set (or powerset) of S, written P(S),
or 2S, is the set of all subsets of S.
Task : By using a library or built-in set type, or by defining
a set type with necessary operations, write a function with a set
S as input that yields the power set 2S of S.
For example, the power set of {1,2,3,4} is
{{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4},
{2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}}.
"""
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import util.
main => go.
% built-in power_set/1 (_much_ faster than power_set/2 defined here)
go =>
P = power_set(1..10),
println(P),
nl.
go2 =>
garbage_collect(100_000_000),
power_set(1..8,P),
println(P),
println(len=P.length),
nl.
power_set(T,PS) =>
PS = [[]] ++ [PP.sort() : PP in findall(P1,power_set(T,[],P1))].remove_dups().sort().
%
% Based on the Prolog solution which use bagof/3 which is
% missing in Picat.
% This gives all possible combinations of the elements in T, with a lot of
% duplicates. This makes is slow and memory consuming.
%
table
power_set(T, PS, PS1) =>
select(E, T, T1),
append(PS, [E], PST),
( PST = PS1; power_set(T1, PS, PS1); power_set(T1, PST, PS1)).
power_set([], [], []) => true.