NAME

List::PowerSet - generate the power set of a list

SYNOPSIS

use List::PowerSet qw(powerset powerset_lazy);

my $ps = powerset(qw(1 2 3));

my $ps_iterator = powerset_lazy(1 .. 1_000);
while(my $set = $ps_iterator->()) {
    # $set is the next powerset entry
}

DESCRIPTION

Suppose you have a list L. The power set of such a list is a list of all the sublists that you can obtain from L by deleting elements from it. For example, the power set of (1, 2, 3) is the list of lists ((), (1), (2), (3), (1, 2), (1, 3), (2, 3), (1, 2, 3)), in some order.

List::PowerSet provides two functions (which are not exported by default, you have to ask for them) to generate power sets.

FUNCTIONS

powerset()

Given a list, powerset() returns an array reference of array references, each referring to a different subset in the powerset of the input list.

my $ps = powerset(qw(1 2 3));

# $ps == [ [1, 2, 3],
#          [   2, 3],
#          [1,    3],
#          [      3],
#          [1, 2   ],
#          [   2   ],
#          [1      ],
#          [       ] ];

powerset_lazy()

Given even a moderately sized input list, powerset() will have to generate a huge result list, taking time and memory to generate. A 20 element input list to powerset() will generate a result list containing 1,048,576 references to other arrays, on average containing 10 items.

powerset_lazy() takes the same input list as powerset(), and returns a subroutine reference. Every time you call through this reference an array reference to a different subset of the powerset is generated and returned.

AUTHORS

Mark Jason Dominus <mjd@plover.com>, Nik Clayton <nik@FreeBSD.org>

The original code was written by Mark.

The module was written by Nik, who discovered mjd's code after failing to find a powerset implementation on CPAN. With mjd's permission he packaged it so that others can easily make use of it.

Copyright 2004 Mark Jason Dominus, and Nik Clayton. All Rights Reserved.

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

BUGS

None known.

Bugs should be reported to via the CPAN RT system. http://rt.cpan.org/NoAuth/ReportBug.html?Queue=List::PowerSet.