GSP
Quick Navigator

Search Site

Unix VPS
A - Starter
B - Basic
C - Preferred
D - Commercial
MPS - Dedicated
Previous VPSs
* Sign Up! *

Support
Contact Us
Online Help
Handbooks
Domain Status
Man Pages

FAQ
Virtual Servers
Pricing
Billing
Technical

Network
Facilities
Connectivity
Topology Map

Miscellaneous
Server Agreement
Year 2038
Credits
 

USA Flag

 

 

Man Pages
List::PowerSet(3) User Contributed Perl Documentation List::PowerSet(3)

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

  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
  }

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.

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      ],
  #          [       ] ];

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.

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.

None known.

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

2004-03-18 perl v5.32.1

Search for    or go to Top of page |  Section 3 |  Main Index

Powered by GSP Visit the GSP FreeBSD Man Page Interface.
Output converted with ManDoc.