--- name: "Math::Combinatorics" section: "3pm" platform: "linux" package: "libmath-combinatorics-perl" version: "0.09-6" release: "Debian 13 (Trixie)" platforms: ["linux"] url: "https://new.carta.tech/Math::Combinatorics" --- # Math::Combinatorics(3pm) Perform combinations and permutations on lists ## 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: different 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 \, 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 argument * 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 for details. You can work around this by making calls to both L and L * 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 ``` ## SEE ALSO 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 ``` ## EXPORTED FUNCTIONS ### combine() ``` Usage : my @combinations = combine($k,@n); Function: implements nCk (n choose k), or n!/(k!*(n-k!)). returns all unique unordered 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 would not be appropriate, use the object-oriented API. See L and the B option. Identical items are assumed to be non-unique. That is, calling C would not be appropriate, use the object-oriented API. See L, and the B option. ``` ### next\_derangement() ``` Usage : my @derangement = $c->next_derangement(); Function: get derangements for @data. Returns : returns a permutation of items from @data (see L), 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 would not be appropriate, use the object-oriented API. See L, and the B option. Identical items are assumed to be non-unique. That is, calling Cnew( 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 permutagenic functions/methods. this is the set elements are chosen from. B: 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 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). 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 } 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). 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 argument is B given to L, otherwise use L. 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). a multiset is a special type of combination where the set from which combinations are drawn contains items that are indistinguishable. use L when a B argument is passed to L. 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 argument is given to L, otherwise use L. 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). 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 argument is B given to L, otherwise use L. 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). a multiset is a special type of permutation where the set from which combinations are drawn contains items that are indistinguishable. use L when a B argument is passed to L. 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 argument is given to L, otherwise use L. 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 ```