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
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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>