/* 

  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 cp.
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.

% using the predicate power_set/2 defined here
go2 =>
  garbage_collect(100_000_000),
  power_set(1..8,P),
  println(P),
  println(len=P.length),
  nl.

%
% using cp:
%  - power_set_cp1: 0/1 version
%  - power_set_cp2: 1..N version
%
go3 =>
  garbage_collect(400_000_000),
  member(N,1..15),
  M = 2**N-1,
  println([n=N,m=M]),
  % Binary version
  PS1 = new_array(M,N),
  PS1 :: 0..1,

  % 1..N
  PS2 = new_array(M,N),
  PS2 :: 0..N,

  power_set_cp1(N,PS1),
  power_set_cp2(N,PS2),

  println("\n0/1"),
  Vars = PS1 ++ PS2,
  solve(Vars),

  foreach(Row in PS1)
    println(Row)
  end,
  nl,
  println("\n1..N"),  
  foreach(Row in PS2)
    println(Row)
  end,
  nl,
  fail,
  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 it 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.
 

% Binary version
power_set_cp1(N, P) =>
  MM = 2**N-1,
  foreach(I in 1..MM)
    to_num([P[I,J] : J in 1..N], 2, I)
  end.

% 1..N
power_set_cp2(N, P) =>
  MM = 2**N-1,
  PS = new_array(MM, N),
  PS :: 0..1,
  power_set_cp1(N,PS),
  foreach(I in 1..MM)
    foreach(J in 1..N)
      P[I,J] #= (N-J+1)*PS[I,J]
    end
  end.


%
% converts a number Num to/from a list of integer List given a base Base
%
to_num(List, Base, Num) =>
   Len = length(List),
   Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]).