Power set: Difference between revisions

{{out}}

<li><p>'''''Use lazy evaluation'''''</p>

If the initial set is quite large, constructing it's powerset can consume lots of memory.

If you want to iterate through all of the elements of the powerset of a set, and don't mind each element being generated immediately before you process it, and being thrown away immediately after you're done with it, you can use vastly less memory.

The following algorithm uses one bit of memory for every element of the original set.

<lang perl>use strict;

use warnings;

sub powerset(&@) {

my $callback = shift;

my $bitmask = '';

my $bytes = @_/8;

{

my @indices = grep vec($bitmask, $_, 1), 0..$#_;

$callback->( @_[@indices] );

++vec($bitmask, $_, 8) and last for 0 .. $bytes;

redo if @indices != @_;

}

}

print "powerset of empty set:\n";

powerset { print "[@_]\n" };

print "powerset of set {1,2,3,4}:\n";

powerset { print "[@_]\n" } 1..4;

my $i = 0;

powerset { ++$i } 1..9;

print "The powerset of a nine element set contains $i elements.\n";

</lang>

{{out}}

<pre>powerset of empty set:

[]

powerset of set {1,2,3,4}:

[]

[1]

[2]

[1 2]

[3]

[1 3]

[2 3]

[1 2 3]

[4]

[1 4]

[2 4]

[1 2 4]

[3 4]

[1 3 4]

[2 3 4]

[1 2 3 4]

The powerset of a nine element set contains 512 elements.

</pre>

The technique shown above will work with arbitrarily large sets, and uses a trivial amount of memory.