Allen Day > Math-Combinatorics > Math::Combinatorics

Download:
Math-Combinatorics-0.09.tar.gz

Dependencies

Annotate this POD (1)

CPAN RT

New  6
Open  0
View/Report Bugs
Module Version: 0.09   Source  

NAME ^

Math::Combinatorics - Perform combinations and permutations on lists

SYNOPSIS ^

Available as an object oriented API.

  use Math::Combinatorics;

  my @n = qw(a b c);
  my $combinat = Math::Combinatorics->new(count => 2,
                                          data => [@n],
                                         );

  print "combinations of 2 from: ".join(" ",@n)."\n";
  print "------------------------".("--" x scalar(@n))."\n";
  while(my @combo = $combinat->next_combination){
    print join(' ', @combo)."\n";
  }

  print "\n";

  print "permutations of 3 from: ".join(" ",@n)."\n";
  print "------------------------".("--" x scalar(@n))."\n";
  while(my @permu = $combinat->next_permutation){
    print join(' ', @permu)."\n";
  }

  output:

Or available via exported functions 'permute', 'combine', and 'factorial'.

  use Math::Combinatorics;

  my @n = qw(a b c);
  print "combinations of 2 from: ".join(" ",@n)."\n";
  print "------------------------".("--" x scalar(@n))."\n";
  print join("\n", map { join " ", @$_ } combine(2,@n)),"\n";
  print "\n";
  print "permutations of 3 from: ".join(" ",@n)."\n";
  print "------------------------".("--" x scalar(@n))."\n";
  print join("\n", map { join " ", @$_ } permute(@n)),"\n";

Output:

  combinations of 2 from: a b c
  ------------------------------
  a b
  a c
  b c

  permutations of 3 from: a b c
  ------------------------------
  a b c
  a c b
  b a c
  b c a
  c a b
  c b a

Output from both types of calls is the same, but the object-oriented approach consumes much less memory for large sets.

DESCRIPTION ^

Combinatorics is the branch of mathematics studying the enumeration, combination, and permutation of sets of elements and the mathematical relations that characterize their properties. As a jumping off point, refer to:

 http://mathworld.wolfram.com/Combinatorics.html

This module provides a pure-perl implementation of nCk, nCRk, nPk, nPRk, !n and n! (combination, multiset, permutation, string, derangement, and factorial, respectively). Functional and object-oriented usages allow problems such as the following to be solved:

combine - nCk
 http://mathworld.wolfram.com/Combination.html

"Fun questions to ask the pizza parlor wait staff: how many possible combinations of 2 toppings can I get on my pizza?".

derange - !n
 http://mathworld.wolfram.com/Derangement.html

"A derangement of n ordered objects, denoted !n, is a permutation in which none of the objects appear in their "natural" (i.e., ordered) place."

permute - nPk
 http://mathworld.wolfram.com/Permutation.html

"Master Mind Game: ways to arrange pieces of different colors in a certain number of positions, without repetition of a color".

Object-oriented usage additionally allows solving these problems by calling "new()" with a frequency vector:

string - nPRk
 http://mathworld.wolfram.com/String.html

"Morse signals: diferent signals of 3 positions using the two symbols - and .".

 $o = Math::Combinatorics->new( count=>3 , data=>[qw(. -)] , frequency=>[3,3] );
 while ( my @x = $o->next_multiset ) {
   my $p = Math::Combinatorics->new( data=>\@x , frequency=>[map{1} @x] );
   while ( my @y = $p->next_string ) {
     #do something
   }
 }
multiset/multichoose - nCRk
 http://mathworld.wolfram.com/Multiset.html

"ways to extract 3 balls at once of a bag with 3 black and 3 white balls".

 $o = Math::Combinatorics->new( count=>3 , data=>[qw(white black)] , frequency=>[3,3] );
 while ( my @x = $o->next_multiset ) {
   #do something
 }

EXPORT

the following export tags will bring a single method into the caller's namespace. no symbols are exported by default. see pod documentation below for method descriptions.

  combine
  derange
  multiset
  permute
  string
  factorial

AUTHOR ^

Allen Day <allenday@ucla.edu>, with algorithmic contributions from Christopher Eltschka and Tye.

Copyright (c) 2004-2005 Allen Day. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

ACKNOWLEDGEMENTS ^

A sincere thanks to everyone for helping to make this a better module. After initial development I've only had time to accept patches and improvements. Math::Combinatorics continues to be developed and improved by the community. Contributors of note include:

For adding new features: Carlos Rica, David Coppit, Carlos Segre, Lyon Lemmens

For bug reports: Ying Yang, Joerg Beyer, Marc Logghe, Yunheng Wang, Torsten Seemann, Gerrit Haase, Joern Behre, Lyon Lemmens, Federico Lucifredi

BUGS / TODO ^

Report them to the author.

 * Need more extensive unit tests.

   * tests for new()'s frequency argment

 * A known bug (more of a missing feature, actually) does not allow parameterization of k
 for nPk in permute().  it is assumed k == n.  L</permute()> for details.  You can work
 around this by making calls to both L</permute()> and L</combine()>

 * Lots of really interesting stuff from Mathworld.Wolfram.com.  MathWorld rocks!  Expect
 to see implementation of more concepts from their site, e.g.:

   http://mathworld.wolfram.com/BellNumber.html
   http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
   http://mathworld.wolfram.com/Word.html

 * Other combinatorics stuff
   http://en.wikipedia.org/wiki/Catalan_number
   http://en.wikipedia.org/wiki/Stirling_number

SEE ALSO ^

Set::Scalar

Set::Bag

String::Combination (alas misnamed, it actually returns permutations on a string).

 http://perlmonks.thepen.com/29374.html

 http://groups.google.com/groups?selm=38568F79.13680B86%40physik.tu-muenchen.de&output=gplain

EXPORTED FUNCTIONS ^

combine()

 Usage   : my @combinations = combine($k,@n);
 Function: implements nCk (n choose k), or n!/(k!*(n-k!)).
           returns all unique unorderd combinations of k items from set n.
           items in n are assumed to be character data, and are
           copied into the return data structure (see "Returns" below).
 Example : my @n = qw(a b c);
           my @c = combine(2,@n);
           print join "\n", map { join " ", @$_ } @c;
           # prints:
           # b c
           # a c
           # a b
 Returns : a list of arrays, where each array contains a unique combination
           of k items from n
 Args    : a list of items to be combined
 Notes   : data is internally assumed to be alphanumeric.  this is necessary
           to efficiently generate combinations of large sets.  if you need
           combinations of non-alphanumeric data, or on data
           C<sort {$a cmp $b}> would not be appropriate, use the
           object-oriented API.  See L</new()> and the B<compare> option.

           Identical items are assumed to be non-unique.  That is, calling
           C<combine(1,'a','a') yields two sets: {a}, and {a}.  See
           L</next_multiset() if this is not the desired behavior.

derange()

 Usage   : my @deranges = derange(@n);
 Function: implements !n, a derangement of n items in which none of the
           items appear in their originally ordered place.
 Example : my @n = qw(a b c);
           my @d = derange(@n);
           print join "\n", map { join " ", @$_ } @d;
           # prints:
           # a c b
           # b a c
           # b c a
           # c a b
           # c b a
 Returns : a list of arrays, where each array contains a derangement of
           k items from n (where k == n).
 Args    : a list of items to be deranged.
 Note    : k should really be parameterizable.  this will happen
           in a later version of the module.  send me a patch to
           make that version come out sooner.
 Notes   : data is internally assumed to be alphanumeric.  this is necessary
           to efficiently generate combinations of large sets.  if you need
           combinations of non-alphanumeric data, or on data
           C<sort {$a cmp $b}> would not be appropriate, use the
           object-oriented API.  See L</new()>, and the B<compare> option.

next_derangement()

 Usage   : my @derangement = $c->next_derangement();
 Function: get derangements for @data.
 Returns : returns a permutation of items from @data (see L</new()>),
           where none of the items appear in their natural order.  repeated calls
           retrieve all unique derangements of @data elements.  a returned empty
           list signifies all derangements have been iterated.
 Args    : none.

factorial()

 Usage   : my $f = factorial(4); #returns 24, or 4*3*2*1
 Function: calculates n! (n factorial).
 Returns : undef if n is non-integer or n < 0
 Args    : a positive, non-zero integer
 Note    : this function is used internally by combine() and permute()

permute()

 Usage   : my @permutations = permute(@n);
 Function: implements nPk (n permute k) (where k == n), or n!/(n-k)!
            returns all unique permutations of k items from set n
           (where n == k, see "Note" below).  items in n are assumed to
           be character data, and are copied into the return data
           structure.
 Example : my @n = qw(a b c);
           my @p = permute(@n);
           print join "\n", map { join " ", @$_ } @p;
           # prints:
           # b a c
           # b c a
           # c b a
           # c a b
           # a c b
           # a b c
 Returns : a list of arrays, where each array contains a permutation of
           k items from n (where k == n).
 Args    : a list of items to be permuted.
 Note    : k should really be parameterizable.  this will happen
           in a later version of the module.  send me a patch to
           make that version come out sooner.
 Notes   : data is internally assumed to be alphanumeric.  this is necessary
           to efficiently generate combinations of large sets.  if you need
           combinations of non-alphanumeric data, or on data
           C<sort {$a cmp $b}> would not be appropriate, use the
           object-oriented API.  See L</new()>, and the B<compare> option.

           Identical items are assumed to be non-unique.  That is, calling
           C<permute('a','a') yields two sets: {a,a}, and {a,a}.  See
           L</next_string() if this is not the desired behavior.

CONSTRUCTOR ^

new()

 Usage   : my $c = Math::Combinatorics->new( count => 2,       #treated as int
                                             data => [1,2,3,4] #arrayref or anonymous array
                                           );
 Function: build a new Math::Combinatorics object.
 Returns : a Math::Combinatorics object
 Args    : count     - required for combinatoric functions/methods.  number of elements to be
                       present in returned set(s).
           data      - required for combinatoric B<AND> permutagenic functions/methods.  this is the
                       set elements are chosen from.  B<NOTE>: this array is modified in place; make
                       a copy of your array if the order matters in the caller's space.
           frequency - optional vector of data frequencies.  must be the same length as the B<data>
                       constructor argument.  These two constructor calls here are equivalent:

                         $a = 'a';
                         $b = 'b';

                         Math::Combinatorics->new( count=>2, data=>[\$a,\$a,\$a,\$a,\$a,\$b,\$b] );
                         Math::Combinatorics->new( count=>2, data=>[\$a,\$b], frequency=>[5,2] );

                       so why use this?  sometimes it's useful to have multiple identical entities in
                       a set (in set theory jargon, this is called a "bag", See L<Set::Bag>).
           compare   - optional subroutine reference used in sorting elements of the set.  examples:

                       #appropriate for character elements
                       compare => sub { $_[0] cmp $_[1] }
                       #appropriate for numeric elements
                       compare => sub { $_[0] <=> $_[1] }
                       #appropriate for object elements, perhaps
                       compare => sub { $_[0]->value <=> $_[1]->value }

                     The default sort mechanism is based on references, and cannot be predicted.
                     Improvements for a more flexible compare() mechanism are most welcome.

OBJECT METHODS ^

next_combination()

 Usage   : my @combo = $c->next_combination();
 Function: get combinations of size $count from @data.
 Returns : returns a combination of $count items from @data (see L</new()>).
           repeated calls retrieve all unique combinations of $count elements.
           a returned empty list signifies all combinations have been iterated.
 Note    : this method may only be used if a B<frequency> argument is B<NOT>
           given to L</new()>, otherwise use L</next_multiset()>.
 Args    : none.

next_multiset()

 Usage   : my @multiset = $c->next_multiset();
 Function: get multisets for @data.
 Returns : returns a multiset of items from @data (see L</new()>).
           a multiset is a special type of combination where the set from which
           combinations are drawn contains items that are indistinguishable.  use
           L</next_multiset()> when a B<frequency> argument is passed to L</new()>.
           repeated calls retrieve all unique multisets of @data elements.  a
           returned empty list signifies all multisets have been iterated.
 Note    : this method may only be used if a B<frequency> argument is given to
           L</new()>, otherwise use L</next_combination()>.
 Args    : none.

next_permutation()

 Usage   : my @permu = $c->next_permutation();
 Function: get permutations of elements in @data.
 Returns : returns a permutation of items from @data (see L</new()>).
           repeated calls retrieve all unique permutations of @data elements.
           a returned empty list signifies all permutations have been iterated.
 Note    : this method may only be used if a B<frequency> argument is B<NOT>
           given to L</new()>, otherwise use L</next_string()>.
 Args    : none.

next_string()

 Usage   : my @string = $c->next_string();
 Function: get strings for @data.
 Returns : returns a multiset of items from @data (see L</new()>).
           a multiset is a special type of permutation where the set from which
           combinations are drawn contains items that are indistinguishable.  use
           L</next_permutation()> when a B<frequency> argument is passed to L</new()>.
           repeated calls retrieve all unique multisets of @data elements.  a
           returned empty list signifies all strings have been iterated.
 Note    : this method may only be used if a B<frequency> argument is given to
           L</new()>, otherwise use L</next_permutation()>.
 Args    : none.

INTERNAL FUNCTIONS AND METHODS ^

sum()

 Usage   : my $sum = sum(1,2,3); # returns 6
 Function: sums a list of integers.  non-integer list elements are ignored
 Returns : sum of integer items in arguments passed in
 Args    : a list of integers
 Note    : this function is used internally by combine()

compare()

 Usage   : $obj->compare()
 Function: internal, undocumented.  holds a comparison coderef.
 Returns : value of compare (a coderef)

count()

 Usage   : $obj->count()
 Function: internal, undocumented.  holds the "k" in nCk or nPk.
 Returns : value of count (an int)

data()

 Usage   : $obj->data()
 Function: internal, undocumented.  holds the set "n" in nCk or nPk.
 Returns : value of data (an arrayref)

swap()

internal, undocumented.

reverse()

internal, undocumented.

rotate()

internal, undocumented.

upper_bound()

internal, undocumented.

lower_bound()

internal, undocumented.

_permutation_cursor()

 Usage   : $obj->_permutation_cursor()
 Function: internal method.  cursor on permutation iterator order.
 Returns : value of _permutation_cursor (an arrayref)
 Args    : none
syntax highlighting: