.\" Automatically generated by Pod::Man 2.22 (Pod::Simple 3.07) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is turned on, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .ie \nF \{\ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . nr % 0 . rr F .\} .el \{\ . de IX .. .\} .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "Math::Combinatorics 3pm" .TH Math::Combinatorics 3pm "2006-12-12" "perl v5.10.1" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::Combinatorics \- Perform combinations and permutations on lists .SH "SYNOPSIS" .IX Header "SYNOPSIS" Available as an object oriented \s-1API\s0. .PP .Vb 1 \& 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)."\en"; \& print "\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-".("\-\-" x scalar(@n))."\en"; \& while(my @combo = $combinat\->next_combination){ \& print join(\*(Aq \*(Aq, @combo)."\en"; \& } \& \& print "\en"; \& \& print "permutations of 3 from: ".join(" ",@n)."\en"; \& print "\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-".("\-\-" x scalar(@n))."\en"; \& while(my @permu = $combinat\->next_permutation){ \& print join(\*(Aq \*(Aq, @permu)."\en"; \& } \& \& output: .Ve .PP Or available via exported functions 'permute', 'combine', and 'factorial'. .PP .Vb 1 \& use Math::Combinatorics; \& \& my @n = qw(a b c); \& print "combinations of 2 from: ".join(" ",@n)."\en"; \& print "\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-".("\-\-" x scalar(@n))."\en"; \& print join("\en", map { join " ", @$_ } combine(2,@n)),"\en"; \& print "\en"; \& print "permutations of 3 from: ".join(" ",@n)."\en"; \& print "\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-\-".("\-\-" x scalar(@n))."\en"; \& print join("\en", map { join " ", @$_ } permute(@n)),"\en"; .Ve .PP Output: .PP .Vb 5 \& 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 .Ve .PP Output from both types of calls is the same, but the object-oriented approach consumes much less memory for large sets. .SH "DESCRIPTION" .IX Header "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: .PP .Vb 1 \& http://mathworld.wolfram.com/Combinatorics.html .Ve .PP 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: .IP "combine \- nCk" 4 .IX Item "combine - nCk" .Vb 1 \& http://mathworld.wolfram.com/Combination.html .Ve .Sp \&\*(L"Fun questions to ask the pizza parlor wait staff: how many possible combinations of 2 toppings can I get on my pizza?\*(R". .IP "derange \- !n" 4 .IX Item "derange - !n" .Vb 1 \& http://mathworld.wolfram.com/Derangement.html .Ve .Sp \&\*(L"A derangement of n ordered objects, denoted !n, is a permutation in which none of the objects appear in their \*(R"natural\*(L" (i.e., ordered) place.\*(R" .IP "permute \- nPk" 4 .IX Item "permute - nPk" .Vb 1 \& http://mathworld.wolfram.com/Permutation.html .Ve .Sp \&\*(L"Master Mind Game: ways to arrange pieces of different colors in a certain number of positions, without repetition of a color\*(R". .PP Object-oriented usage additionally allows solving these problems by calling \*(L"\fInew()\fR\*(R" with a \fBfrequency\fR vector: .IP "string \- nPRk" 4 .IX Item "string - nPRk" .Vb 1 \& http://mathworld.wolfram.com/String.html .Ve .Sp \&\*(L"Morse signals: diferent signals of 3 positions using the two symbols \- and .\*(R". .Sp .Vb 7 \& $o = Math::Combinatorics\->new( count=>3 , data=>[qw(. \-)] , frequency=>[3,3] ); \& while ( my @x = $o\->next_multiset ) { \& my $p = Math::Combinatorics\->new( data=>\e@x , frequency=>[map{1} @x] ); \& while ( my @y = $p\->next_string ) { \& #do something \& } \& } .Ve .IP "multiset/multichoose \- nCRk" 4 .IX Item "multiset/multichoose - nCRk" .Vb 1 \& http://mathworld.wolfram.com/Multiset.html .Ve .Sp \&\*(L"ways to extract 3 balls at once of a bag with 3 black and 3 white balls\*(R". .Sp .Vb 4 \& $o = Math::Combinatorics\->new( count=>3 , data=>[qw(white black)] , frequency=>[3,3] ); \& while ( my @x = $o\->next_multiset ) { \& #do something \& } .Ve .SS "\s-1EXPORT\s0" .IX Subsection "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. .PP .Vb 6 \& combine \& derange \& multiset \& permute \& string \& factorial .Ve .SH "AUTHOR" .IX Header "AUTHOR" Allen Day , with algorithmic contributions from Christopher Eltschka and Tye. .PP 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. .SH "ACKNOWLEDGEMENTS" .IX Header "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: .PP For adding new features: Carlos Rica, David Coppit, Carlos Segre, Lyon Lemmens .PP For bug reports: Ying Yang, Joerg Beyer, Marc Logghe, Yunheng Wang, Torsten Seemann, Gerrit Haase, Joern Behre, Lyon Lemmens, Federico Lucifredi .SH "BUGS / TODO" .IX Header "BUGS / TODO" Report them to the author. .PP .Vb 1 \& * Need more extensive unit tests. \& \& * tests for new()\*(Aqs 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 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 .Ve .SH "SEE ALSO" .IX Header "SEE ALSO" Set::Scalar .PP Set::Bag .PP String::Combination (alas misnamed, it actually returns permutations on a string). .PP .Vb 1 \& http://perlmonks.thepen.com/29374.html \& \& http://groups.google.com/groups?selm=38568F79.13680B86%40physik.tu\-muenchen.de&output=gplain .Ve .SH "EXPORTED FUNCTIONS" .IX Header "EXPORTED FUNCTIONS" .SS "\fIcombine()\fP" .IX Subsection "combine()" .Vb 10 \& 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 "\en", 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. .Ve .SS "\fInext_derangement()\fP" .IX Subsection "next_derangement()" .Vb 7 \& 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. .Ve .SS "\fIfactorial()\fP" .IX Subsection "factorial()" .Vb 5 \& 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() .Ve .SS "\fIpermute()\fP" .IX Subsection "permute()" .Vb 10 \& 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 "\en", 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\*(Aqs 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 = \*(Aqa\*(Aq; \& $b = \*(Aqb\*(Aq; \& \& Math::Combinatorics\->new( count=>2, data=>[\e$a,\e$a,\e$a,\e$a,\e$a,\e$b,\e$b] ); \& Math::Combinatorics\->new( count=>2, data=>[\e$a,\e$b], frequency=>[5,2] ); \& \& so why use this? sometimes it\*(Aqs 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. .Ve .SH "OBJECT METHODS" .IX Header "OBJECT METHODS" .SS "\fInext_combination()\fP" .IX Subsection "next_combination()" .Vb 8 \& 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. .Ve .SS "\fInext_multiset()\fP" .IX Subsection "next_multiset()" .Vb 11 \& 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. .Ve .SS "\fInext_permutation()\fP" .IX Subsection "next_permutation()" .Vb 8 \& 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. .Ve .SS "\fInext_string()\fP" .IX Subsection "next_string()" .Vb 11 \& 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. .Ve .SH "INTERNAL FUNCTIONS AND METHODS" .IX Header "INTERNAL FUNCTIONS AND METHODS" .SS "\fIsum()\fP" .IX Subsection "sum()" .Vb 5 \& 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() .Ve .SS "\fIcompare()\fP" .IX Subsection "compare()" .Vb 3 \& Usage : $obj\->compare() \& Function: internal, undocumented. holds a comparison coderef. \& Returns : value of compare (a coderef) .Ve .SS "\fIcount()\fP" .IX Subsection "count()" .Vb 3 \& Usage : $obj\->count() \& Function: internal, undocumented. holds the "k" in nCk or nPk. \& Returns : value of count (an int) .Ve .SS "\fIdata()\fP" .IX Subsection "data()" .Vb 3 \& Usage : $obj\->data() \& Function: internal, undocumented. holds the set "n" in nCk or nPk. \& Returns : value of data (an arrayref) .Ve .SS "\fIswap()\fP" .IX Subsection "swap()" internal, undocumented. .SS "\fIreverse()\fP" .IX Subsection "reverse()" internal, undocumented. .SS "\fIrotate()\fP" .IX Subsection "rotate()" internal, undocumented. .SS "\fIupper_bound()\fP" .IX Subsection "upper_bound()" internal, undocumented. .SS "\fIlower_bound()\fP" .IX Subsection "lower_bound()" internal, undocumented. .SS "\fI_permutation_cursor()\fP" .IX Subsection "_permutation_cursor()" .Vb 4 \& Usage : $obj\->_permutation_cursor() \& Function: internal method. cursor on permutation iterator order. \& Returns : value of _permutation_cursor (an arrayref) \& Args : none .Ve