Data::PowerSet - Generate all subsets of a list of elements

Data-PowerSet documentation Contained in the Data-PowerSet distribution.

Index

Code Index:

NAME

Top

Data::PowerSet - Generate all subsets of a list of elements

VERSION

Top

This document describes version 0.05 of Data::PowerSet, released 2008-05-13.

SYNOPSIS

Top

  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

DESCRIPTION

Top

Data::PowerSet takes a list and returns all possible combinations of the elements appearing in the list without replacement.

EXPORTABLE FUNCTIONS

Top

powerset

The 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 ]] );

METHODS

Top

The object-oriented interface provided by the module is implemented with the following methods.

new

Creates a new 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.

min

Minimum number of elements present in the selection.

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.

max

Maximum number of elements present in the selection.

  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

Perform a 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.

next

Returns a reference to an array containing the next combination of elements from the original list;

    my $ps = Data::PowerSet->new(qw(e t a i s o n));
    my $first = $ps->next;
    my $next  = $ps->next;
reset

Restart from the first combination of the list.

data

Accept a new list of elements from which to draw combinations.

  $ps->data( qw(all new elements to use) );
count

Returns the number of elements in the set. This can be used to set 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.

DIAGNOSTICS

Top

None.

NOTES

Top

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.

SEE ALSO

Top

List::PowerSet

Another module that generates power sets. If I had managed to find it in a search beforehand, I probably would have used it instead. Nonetheless, Data::PowerSet has a couple of features not present in List::PowerSet, but otherwise both can be used pretty much interchangeably.

Algorithm::Combinatorics

A fast (no stacks, no recursion) method for generating permutations and combinations of a set. A power set is merely the union of all combinations (of differing lengths).

http://en.wikipedia.org/wiki/Power_set

The wikipedia definition of a power set.

BUGS

Top

None known. Please report all bugs at http://rt.cpan.org/NoAuth/Bugs.html?Dist=Data-PowerSet (rt.cpan.org)

Make sure you include the output from the following two commands:

  perl -MData::PowerSet -le 'print Data::PowerSet::VERSION'
  perl -V

ACKNOWLEDGEMENTS

Top

This module is dedicated to Estelle Souche, who pointed out the very elegant and obvious algorithm. Smylers suggested the name.

AUTHOR

Top

David Landgren, copyright (C) 2005-2008. All rights reserved.

http://www.landgren.net/perl/

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?

LICENSE

Top

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

Data-PowerSet documentation Contained in the Data-PowerSet distribution. 
# Data::PowerSet.pm
#
# Copyright (c) 2005-2008 David Landgren
# All rights reserved

package Data::PowerSet;

use strict;
use Exporter;

use vars qw/$VERSION @ISA @EXPORT_OK/;
$VERSION = '0.05';
@ISA     = ('Exporter');


push @EXPORT_OK, 'powerset';
sub powerset {
    my %args;
    if (ref($_[0]) eq 'HASH') {
        %args = %{shift @_};
    }
    my @list = ref($_[0]) eq 'ARRAY' ? @{shift @_} : @_;

    $args{min} = exists $args{min} ?  $args{min} <     0 ?     0 : $args{min} :     0;
    $args{max} = exists $args{max} ?  $args{max} > @list ? @list : $args{max} : @list;

    ($args{min}, $args{max}) = ($args{max}, $args{min})
        if $args{max} < $args{min};

    my $lim = 2 ** @list - 1;
    my @powerset;
    while( $lim >= 0 ) {
        my @set;
        my $mask   = $lim--;
        my $offset = 0;
        while( $mask ) {
            push @set, $list[$offset] if $mask & 1;
            $mask >>= 1;
            ++$offset;
        }
        if( @set >= $args{min} and @set <= $args{max} ) {
            push @powerset, exists $args{join}
                ? join( $args{join}, @set)
                : [@set];
        }
    }
    return \@powerset;
}


sub new {
    my $class = shift;
    my %args;
    if( ref($_[0]) eq 'HASH' ) {
        %args = %{shift(@_)};
    }
    if( ref($_[0]) eq 'ARRAY' ) {
        $args{data} = shift @_;
    }
    else {
        $args{data} = [@_],
    }
    $args{current} = 2**@{$args{data}}-1;

    $args{min} =
        exists $args{min}
        ?  $args{min} < 0
            ? 0 : $args{min}
        : 0
    ;

    $args{max} =
        exists $args{max}
        ?  $args{max} > @{$args{data}}
            ? @{$args{data}} : $args{max}
        : @{$args{data}}
    ;

    ($args{min}, $args{max}) = ($args{max}, $args{min})
        if $args{max} < $args{min};
    return bless \%args, $class;
}


sub next {
    my $self = shift;
    my $ok = 0;
    my @set;
    until( $ok ) {
        return undef unless $self->{current} >= 0;
        my $mask   = $self->{current}--;
        my $offset = 0;
        @set = ();
        while( $mask ) {
            push @set, $self->{data}[$offset] if $mask & 1;
            $mask >>= 1;
            ++$offset;
        }
        $ok = 1 if @set >= $self->{min} and @set <= $self->{max};
    }
    return exists $self->{join} ? join($self->{join}, @set) : \@set;
}


sub reset {
    my $self = shift;
    $self->{current} = 2**@{$self->{data}}-1;
}


sub data {
    my $self = shift;
    $self->{data} = [@_],
    $self->{current} = 2**@{$self->{data}}-1;

    $self->{min} = @{$self->{data}} if $self->{min} > @{$self->{data}};
    $self->{max} = @{$self->{data}} if $self->{max} > @{$self->{data}};
}


sub count {
    my $self = shift;
    return scalar(@{$self->{data}});
}


'The Lusty Decadent Delights of Imperial Pompeii';