The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-Combinatorics-0.03
River stage two • 5 direct dependents • 19 total dependents
5 ++
/ Math::Combinatorics

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 "combinations of 2 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

  combinations of 2 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, nPk, and n! (combination, permutation, and factorial, respectively).

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
  permute
  factorial

AUTHOR

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

BUGS

report them to the author. a known bug (partial implementation bug) does not allow parameterization of k for nPk in permute(). it is assumed k == n. "permute()" for details.

SEE ALSO

Set::Scalar

Set::Bag

String::Combination (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 FUCTIONS

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.

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.

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()

METHODS

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.
           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 }

                     defaults to "sub { $_[0] cmp $_[1] }"

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