Power set
You are encouraged to solve this task according to the task description, using any language you may know.
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 seen 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 build-in set type, or defining a set type with necessary operations, write a function with a set S as input that yields a power set 2S of S.
D
<d>module powset ; import std.stdio, std.format : fmx = format ;
class Set(T) {
alias Set!(T) Z ;
alias bool[T] S ;
final class SubSet {
private bool[] include ;
private void reset() { include = new bool[](length) ;}
private bool hasNext() {
bool carry = true ;
foreach( inout b ; include)
if(carry) {
if(b) b = false ;
else {
b = true ;
carry = false ;
}
} else
break ;
return !carry ;
}
private Z next() {
Z z = new Z ;
foreach(i,k ; members)
if(include[i])
z.add(k) ;
return z ;
}
int opApply(int delegate(inout Z) dg) {
Z nxt ;
reset() ;
do {
nxt = next ;
if(dg(nxt)) break ;
} while (hasNext) ;
return 1 ;
}
}
private S set ;
private SubSet subset ;
this() { subset = new SubSet ;}
this(T[] k) { add(k) ; this() ; }
void add(T k) { set[k] = true ; }
void add(T[] k) { foreach(e ; k) add(e) ; }
T[] members() { return set.keys.sort ; }
uint length() { return set.length ; }
string toString() { return fmx("<%s>", fmx("%s", members)[1..$-1]) ; }
int opCmp(Object LHS) { // trivial compare so that this type can be a key
Z lhs = cast(Z) LHS ;
if(lhs) return length - lhs.length ;
return 0 ;
}
SubSet subSet() { return subset ; }
}
Set!(Set!(T)) powSet(T)(Set!(T) set) {
Set!(Set!(T)) ps = new Set!(Set!(T)) ;
foreach(ss ; set.subSet)
ps.add(ss) ;
return ps ;
}
void main() {
Set!(int) iset = new Set!(int) ;
iset.add([1,2,3]) ; writefln(iset) ; writefln(powSet(iset)) ;
}</d>