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

name
synopsis
description
commands
bugs, ideas, feedback
category

NAME

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

SYNOPSIS

       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

________________________________________________________________________________________________________________

DESCRIPTION

       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
       [http://mathworld.wolfram.com]

COMMANDS

::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 when

exp( 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.

::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.

::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.

::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.

::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

::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

::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

::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

::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.

::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.

::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.

::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.

::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.

::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.

$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.

$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.

$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.

$combin setElements
Return the next combination of the registered items.

BUGS, IDEAS, FEEDBACK

       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 [http://core.tcl.tk/tcllib/reportlist].  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.

NAME

SYNOPSIS

DESCRIPTION

COMMANDS

BUGS, IDEAS, FEEDBACK

CATEGORY