# 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``````

Set::Scalar

Set::Bag

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

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

# 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 { \$_ cmp \$_ }
#appropriate for numeric elements
compare => sub { \$_ <=> \$_ }
#appropriate for object elements, perhaps
compare => sub { \$_->value <=> \$_->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``````