Power set: Difference between revisions

Line 607:

=={{header|D}}==

Version using just arrays (it assumes the input to contain distinct items):

<lang d>T[][] powerSet(T)(in T[] s) pure nothrow {

<lang d>T[][] powerSet(T)(in T[] s) pure nothrow @safe {

auto r = new typeof(return)(1, 0);

foreach (e; s) {

Line 620:

void main() {

import std.stdio;

[1, 2, 3].powerSet.writeln;

}</lang>

Line 627:

Line 628:

===Lazy Version===

Compile with -version=power_set2_main to run the main.

<lang d>auto powerSet(T)(T[] xs) pure nothrow {

<lang d>auto powerSet(T)(T[] xs) pure nothrow @safe {

⚫

static struct Result {

⚫

~~auto~~ output = ~~new T[xs~~.length];

~~immutable~~ ~~size_t~~ ~~len~~ = 1U << ~~xs.length~~;

T[] xsLocal, output;

size_t len;

⚫

struct Result {

size_t bits;

⚫

@property empty() const pure nothrow { ~~return bits == len; }~~

⚫

void popFront() pure nothrow { bits++; }

⚫

@property save() pure nothrow { return this; }

T[] ~~front(~~) nothrow {

this(T[] xs_) pure nothrow @safe {

this.xsLocal = xs_;

⚫

this.output.length = xs_.length;

this.len = 1U << xs_.length;

}

⚫

@property empty() const pure nothrow @safe {

return bits == len;

}

⚫

void popFront() pure nothrow @safe { bits++; }

⚫

@property save() pure nothrow @safe { return this; }

T[] front() pure nothrow @safe {

size_t pos = 0;

foreach (immutable size_t i; 0 .. xs.length)

foreach (immutable size_t i; 0 .. xsLocal.length)

if (bits & (1 << i))

output[pos++] = xs[i];

output[pos++] = xsLocal[i];

return output[0 .. pos];

}

return Result();

return Result(xs);

}