Rosetta Code

Power set: Difference between revisions

Page Discussion

Power set (view source)

Revision as of 03:25, 21 April 2015

334 bytes removed ,  9 years ago
→‎{{header|D}}: Move content from subpage
(→‎{{header|D}}: Move content from subpage)
Line 662:
 
=={{header|D}}==
This implementation defines a range which *lazily* enumerates the power set.
Version using just arrays (it assumes the input to contain distinct items):
<lang d>T[][] powerSet(T)(in T[] s) pure nothrow @safe {
auto r = new typeof(return)(1, 0);
foreach (e; s) {
typeof(return) rs;
foreach (x; r)
rs ~= x ~ [e];
r ~= rs;
}
return r;
}
 
<lang d>import std.algorithm;
void main() {
import std.stdiorange;
 
auto powerSet(R)(R r)
[1, 2, 3].powerSet.writeln;
{
return
(1L<<r.length)
.iota
.map!(i =>
r.enumerate
.filter!(t => (1<<t[0]) & i)
.map!(t => t[1])
);
}
 
void main(string[] args)
{
import std.stdio;
args[1..$].powerSet.each!writeln;
}</lang>
{{out}}
<pre>[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]</pre>
 
An alternative version, which implements the range construct from scratch:
===Lazy Version===
Compile with -version=power_set2_main to run the main.
<lang d>auto powerSet(T)(T[] xs) pure nothrow @safe {
static struct Result {
T[] xsLocal, output;
size_t len;
size_t bits;
 
<lang d>import std.range;
this(T[] xs_) pure nothrow @safe {
this.xsLocal = xs_;
this.output.length = xs_.length;
this.len = 1U << xs_.length;
}
 
struct PowerSet(R)
@property empty() const pure nothrow @safe {
if (isRandomAccessRange!R)
return bits == len;
{
}
R r;
size_t position;
 
struct PowerSetItem
void popFront() pure nothrow @safe { bits++; }
{
@property save() pure nothrow @safe { return this; }
R r;
size_t position;
 
private void advance()
T[] front() pure nothrow @safe {
{
size_t pos = 0;
while (!(position & 1))
foreach (immutable size_t i; 0 .. xsLocal.length)
{
if (bits & (1 << i))
r.popFront();
output[pos++] = xsLocal[i];
position >>= 1;
return output[0 .. pos];
}
}
}
}
 
@property bool empty() { return Result(xs)position == 0; }
@property auto front()
{
advance();
return r.front;
}
void popFront()
{
advance();
r.popFront();
position >>= 1;
}
}
 
@property bool empty() { return position == (1 << r.length); }
@property PowerSetItem front() { return PowerSetItem(r.save, position); }
void popFront() { position++; }
}
 
auto powerSet(R)(R r) { return PowerSet!R(r); }</lang>
version (power_set2_main) {
{{out}}
void main() {
<pre>$ rdmd powerset a b c
import std.stdio;
[]
[1, 2, 3].powerSet.writeln;
["a"]
}
["b"]
}</lang>
["a", "b"]
Same output.
["c"]
 
["a", "c"]
A [[Power_set/D|set implementation]] and its power set function.
["b", "c"]
["a", "b", "c"]</pre>
 
=={{header|Déjà Vu}}==
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/74395"