NAME

Math::Combinatorics - Perform combinations and permutations on lists

SYNOPSIS

use Math::Combinatorics qw(combine permute);

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
------------------------------
b c
a c
a b

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

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>

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

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

METHODS

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 can be scalars, or references... whatever.  they 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

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 can be scalars,
          references... whatever.  they 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.

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 < 1
Args    : a positive, non-zero integer
Note    : this function is used internally by combine() and permute()

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