[ Tcllib Home | Main Table Of Contents | Table Of Contents | Keyword Index | Categories | Modules | Applications ]

math::combinatorics - Combinatorial functions in the Tcl Math Library

- package require
**Tcl 8.2** - package require
**math ?1.2.3?** - package require
**Tcl 8.6** - package require
**TclOO** - package require
**math::combinatorics ?2.0?**

**::math::ln_Gamma***z***::math::factorial***x***::math::choose***n k***::math::Beta***z w***::math::combinatorics::permutations***n***::math::combinatorics::variations***n**k***::math::combinatorics::combinations***n**k***::math::combinatorics::derangements***n***::math::combinatorics::catalan***n***::math::combinatorics::firstStirling***n**m***::math::combinatorics::secondStirling***n**m***::math::combinatorics::partitionP***n***::math::combinatorics::list-permutations***n***::math::combinatorics::list-variations***n**k***::math::combinatorics::list-combinations***n**k***::math::combinatorics::list-derangements***n***::math::combinatorics::list-powerset***n***::math::combinatorics::permutationObj**new/create NAME*n***$perm**next**$perm**reset**$perm**setElements*elements***$perm**setElements**::math::combinatorics::combinationObj**new/create NAME*n**k***$combin**next**$combin**reset**$combin**setElements*elements***$combin**setElements

The **math** package
contains implementations of several functions useful in
combinatorial problems. The **math::combinatorics** extends the collections based on
features in Tcl 8.6. Note: the meaning of the partitionP function,
Catalan and Stirling numbers is explained on the MathWorld website

**::math::ln_Gamma***z*-
Returns the natural logarithm of the Gamma function for the argument

*z*.The Gamma function is defined as the improper integral from zero to positive infinity of

t**(x-1)*exp(-t) dt

The approximation used in the Tcl Math Library is from Lanczos,

*ISIAM J. Numerical Analysis, series B,*volume 1, p. 86. For "**x**> 1", the absolute error of the result is claimed to be smaller than 5.5*10**-10 -- that is, the resulting value of Gamma whenexp( ln_Gamma( x) )

is computed is expected to be precise to better than nine significant figures.

**::math::factorial***x*-
Returns the factorial of the argument

*x*.For integer

*x*, 0 <=*x*<= 12, an exact integer result is returned.For integer

*x*, 13 <=*x*<= 21, an exact floating-point result is returned on machines with IEEE floating point.For integer

*x*, 22 <=*x*<= 170, the result is exact to 1 ULP.For real

*x*,*x*>= 0, the result is approximated by computing*Gamma(x+1)*using the**::math::ln_Gamma**function, and the result is expected to be precise to better than nine significant figures.It is an error to present

*x*<= -1 or*x*> 170, or a value of*x*that is not numeric. **::math::choose***n k*-
Returns the binomial coefficient

*C(n, k)*C(n,k) = n! / k! (n-k)!

If both parameters are integers and the result fits in 32 bits, the result is rounded to an integer.

Integer results are exact up to at least

*n*= 34. Floating point results are precise to better than nine significant figures. **::math::Beta***z w*-
Returns the Beta function of the parameters

*z*and*w*.Beta(z,w) = Beta(w,z) = Gamma(z) * Gamma(w) / Gamma(z+w)

Results are returned as a floating point number precise to better than nine significant digits provided that

*w*and*z*are both at least 1. **::math::combinatorics::permutations***n*-
Return the number of permutations of n items. The returned number is always an integer, it is not limited by the range of 32-or 64-bits integers using the arbitrary precision integers available in Tcl 8.5 and later.

- int
*n* -
The number of items to be permuted.

- int
**::math::combinatorics::variations***n**k*-
Return the number of variations k items selected from the total of n items. The order of the items is taken into account.

- int
*n* -
The number of items to be selected from.

- int
*k* -
The number of items to be selected in each variation.

- int
**::math::combinatorics::combinations***n**k*-
Return the number of combinations of k items selected from the total of n items. The order of the items is not important.

- int
*n* -
The number of items to be selected from.

- int
*k* -
The number of items to be selected in each combination.

- int
**::math::combinatorics::derangements***n*-
Return the number of derangements of n items. A derangement is a permutation where each item is displaced from the original position.

- int
*n* -
The number of items to be rearranged.

- int
**::math::combinatorics::catalan***n*-
Return the n'th Catalan number. The number n is expected to be 1 or larger. These numbers occur in various combinatorial problems.

- int
*n* -
The index of the Catalan number

- int
**::math::combinatorics::firstStirling***n**m*-
Calculate a Stirling number of the first kind (signed version, m cycles in a permutation of n items)

- int
*n* -
Number of items

- int
*m* -
Number of cycles

- int
**::math::combinatorics::secondStirling***n**m*-
Calculate a Stirling number of the second kind (m non-empty subsets from n items)

- int
*n* -
Number of items

- int
*m* -
Number of subsets

- int
**::math::combinatorics::partitionP***n*-
Calculate the number of ways an integer n can be written as the sum of positive integers.

- int
*n* -
Number in question

- int
**::math::combinatorics::list-permutations***n*-
Return the list of permutations of the numbers 0, ..., n-1.

- int
*n* -
The number of items to be permuted.

- int
**::math::combinatorics::list-variations***n**k*-
Return the list of variations of k numbers selected from the numbers 0, ..., n-1. The order of the items is taken into account.

- int
*n* -
The number of items to be selected from.

- int
*k* -
The number of items to be selected in each variation.

- int
**::math::combinatorics::list-combinations***n**k*-
Return the list of combinations of k numbers selected from the numbers 0, ..., n-1. The order of the items is ignored.

- int
*n* -
The number of items to be selected from.

- int
*k* -
The number of items to be selected in each combination.

- int
**::math::combinatorics::list-derangements***n*-
Return the list of derangements of the numbers 0, ..., n-1.

- int
*n* -
The number of items to be rearranged.

- int
**::math::combinatorics::list-powerset***n*-
Return the list of all subsets of the numbers 0, ..., n-1.

- int
*n* -
The number of items to be rearranged.

- int
**::math::combinatorics::permutationObj**new/create NAME*n*-
Create a TclOO object for returning permutations one by one. If the last permutation has been reached an empty list is returned.

- int
*n* -
The number of items to be rearranged.

- int
**$perm**next-
Return the next permutation of n objects.

**$perm**reset-
Reset the object, so that the command

*next*returns the complete list again. **$perm**setElements*elements*-
Register a list of items to be permuted, using the

*nextElements*command.- list
*elements* -
The list of n items that will be permuted.

- list
**$perm**setElements-
Return the next permulation of the registered items.

**::math::combinatorics::combinationObj**new/create NAME*n**k*-
Create a TclOO object for returning combinations one by one. If the last combination has been reached an empty list is returned.

- int
*n* -
The number of items to be rearranged.

- int
**$combin**next-
Return the next combination of n objects.

**$combin**reset-
Reset the object, so that the command

*next*returns the complete list again. **$combin**setElements*elements*-
Register a list of items to be permuted, using the

*nextElements*command.- list
*elements* -
The list of n items that will be permuted.

- list
**$combin**setElements-
Return the next combination of the registered items.

This document, and the package it describes, will undoubtedly
contain bugs and other problems. Please report such in the category
*math* of the Tcllib Trackers. Please
also report any ideas for enhancements you may have for either
package and/or documentation.

When proposing code changes, please provide *unified
diffs*, i.e the output of **diff -u**.

Note further that *attachments* are strongly preferred
over inlined patches. Attachments can be made by going to the
**Edit** form of the ticket immediately after its
creation, and then using the left-most button in the secondary
navigation bar.

Mathematics