Power set: Difference between revisions
Content added Content deleted
(+D) |
m (→{{header|D}}: remove sort in members function, which require T to be sortable, and remove also opCmp) |
||
Line 49: | Line 49: | ||
void add(T k) { set[k] = true ; } |
void add(T k) { set[k] = true ; } |
||
void add(T[] k) { foreach(e ; k) add(e) ; } |
void add(T[] k) { foreach(e ; k) add(e) ; } |
||
T[] members() { return set.keys |
T[] members() { return set.keys ; } |
||
uint length() { return set.length ; } |
uint length() { return set.length ; } |
||
string toString() { return fmx("<%s>", fmx("%s", members)[1..$-1]) ; } |
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 ; } |
SubSet subSet() { return subset ; } |
||
} |
} |
Revision as of 18:36, 7 June 2008
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>