Math::Combinatorics - Perform combinations and permutations on lists
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.
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). Functional and object-oriented usages allow problems such as the following to be solved:
"Fun questions to ask the pizza parlor wait staff: how many possible combinations of 2 toppings can I get on my pizza?".
"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:
"morse signals: diferent signals of 3 positions using the 2 two symbol - and .".
my $c = Math::Combinatorics->new( count => 3, data => ['a','b'], frequency => [3,3], ); while (my @x = $c->next_combination) { my $d = Math::Combinatorics->new( data => \@x ); while (my @y = $d->next_permutation) { print "@y\n"; } }
"different words obtained permuting the letters of the word PARROT".
"ways to extract 3 balls at once of a bag with black and white balls".
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
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.
Thanks to everyone for helping to make this a better module.
For adding new features: Carlos Rica, David Coppit
For bug reports: Ying Yang, Joerg Beyer, Marc Logghe
Report them to the author.
* A known bug (more of a missing feature, actually) does not allow parameterization of k for nPk in permute(). it is assumed k == n. "permute()" for details. You can work around this by making calls to both "permute()" and "combine()"
* No implementation of Stirling Numbers of the Second Kind, or Bell Numbers.
http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
http://mathworld.wolfram.com/BellNumber.html
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
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.
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.
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()
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 } defaults to "sub { $_[0] cmp $_[1] }"
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.
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.
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()
Usage : $obj->compare() Function: internal, undocumented. holds a comparison coderef. Returns : value of compare (a coderef)
Usage : $obj->count() Function: internal, undocumented. holds the "k" in nCk or nPk. Returns : value of count (an int)
Usage : $obj->data() Function: internal, undocumented. holds the set "n" in nCk or nPk. Returns : value of data (an arrayref)
internal, undocumented.
Usage : $obj->_permutation_cursor() Function: internal method. cursor on permutation iterator order. Returns : value of _permutation_cursor (an arrayref) Args : none
To install Math::Combinatorics, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::Combinatorics
CPAN shell
perl -MCPAN -e shell install Math::Combinatorics
For more information on module installation, please visit the detailed CPAN module installation guide.