|
Data::PowerSet - Generate all subsets of a list of elements |
Data::PowerSet - Generate all subsets of a list of elements
This document describes version 0.04 of Data::PowerSet, released 2007-04-10.
use Data::PowerSet 'powerset';
my $powerset = powerset( 3, 1, 4 );
for my $p (@$powerset) {
print "@$p\n";
}
# prints 3 1 4 1 4 3 4 4 3 1 1 3
An object-oriented interface is also available;
my $d = Data::PowerSet->new( 3, 1, 4 );
while (my $r = $d->next) {
print "@$r\n";
}
# produces the same output as above
Data::PowerSet takes a list and returns all possible
combinations of the elements appearing in the list without replacement.
powerset function takes an array (or a reference to an array) on
input and returns a reference to an array of arrays containing all the
possible unique combinations of elements.
It is also possible to supply a reference to hash as the first
parameter to tweak the behaviour. See the new method for a
description of what keys can be specified.
powerset( 2, 5, 10, 17 );
powerset( {min => 1}, qw(a b c d) );
powerset( [qw[ bodine mondaugen gadrulfi fleische eigenvalue ]] );
The object-oriented interface provided by the module is implemented with the following methods.
Data::PowerSet object.
my $ps = Data::PowerSet->new( qw( foo bar grault waldo ));
A reference to a hash may be supplied, to change the way the object behaves.
Note that the empty set (no elements) is quite valid, according to
the mathematical definition of a power set. If this is not what you
expect, setting min to 1 will effectively cause the empty set to
be excluded from the result.
my $ps = Data::PowerSet->new( {min=>2}, 2, 3, 5, 8, 11 );
In the above object, no returned list will contain fewer than 2 elements.
my $ps = Data::PowerSet->new( {max=>3}, 2, 3, 5, 8, 11 );
In the above object, no returned list will contain more than 3 elements.
join() on each returned list using the
specified value.
my $ps = Data::Powerset->new( {join=>'-'}, 'a', 'b' );
When this attribute is used, the next() method will
return a scalar rather than a reference to an array.
my $ps = Data::PowerSet->new(qw(e t a i s o n));
my $first = $ps->next;
my $next = $ps->next;
$ps->data( qw(all new elements to use) );
max to the number of elements minus one, in order to
exclude the set of all elements, when the number of elements
is difficult to determine beforehand.
None.
Power sets grow exponentially. A power set of 10 elements returns a more than one thousand results. A power set of 20 elements contains more than one million results. The module is not expected to be put to use in larger sets.
A power set, by definition, includes the set of no elements and
the set of all elements. If these results are not desired, the
min and max methods or properties can be used to exclude
them from the results.
This module works with perl version 5.005_04 and above.
Data::PowerSet has a couple of features not
present in List::PowerSet, but otherwise both can be used
pretty much interchangeably.
None known. Please report all bugs at http://rt.cpan.org/NoAuth/Bugs.html
Make sure you include the output from the following two commands:
perl -MData::PowerSet -le 'print Data::PowerSet::VERSION' perl -V
This module is dedicated to Estelle Souche, who pointed out the very elegant and obvious algorithm. Smylers suggested the name.
David Landgren, copyright (C) 2005-2007. All rights reserved.
If you (find a) use this module, I'd love to hear about it. If you want to be informed of updates, send me a note. You know my first name, you know my domain. Can you guess my e-mail address?
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.
|
Data::PowerSet - Generate all subsets of a list of elements |