  Quick Navigator

 Search Site Miscellaneous Server Agreement Year 2038 Credits   Math::Combinatorics(3) User Contributed Perl Documentation Math::Combinatorics(3)

# 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
```
 2006-12-12 perl v5.28.1

Search for    or go to Top of page |  Section 3 |  Main Index Visit the GSP FreeBSD Man Page Interface.
Output converted with ManDoc.