Power set
Power set
You are encouraged to solve this task according to the task description, using any language you may know.
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 ; } uint length() { return set.length ; } string toString() { return fmx("<%s>", fmx("%s", members)[1..$-1]) ; } 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>