1math::combinatorics(n) Tcl Math Library math::combinatorics(n)
2______________________________________________________________________________
6
8 math::combinatorics - Combinatorial functions in the Tcl Math Library
9
11 package require Tcl 8.2
12 package require math ?1.2.3?
14 package require Tcl 8.6
16 package require TclOO
18 package require math::combinatorics ?2.0?
20 ::math::ln_Gamma z
22 ::math::factorial x
24 ::math::choose n k
26 ::math::Beta z w
28 ::math::combinatorics::permutations n
30 ::math::combinatorics::variations n k
32 ::math::combinatorics::combinations n k
34 ::math::combinatorics::derangements n
36 ::math::combinatorics::catalan n
38 ::math::combinatorics::firstStirling n m
40 ::math::combinatorics::secondStirling n m
42 ::math::combinatorics::partitionP n
44 ::math::combinatorics::list-permutations n
46 ::math::combinatorics::list-variations n k
48 ::math::combinatorics::list-combinations n k
50 ::math::combinatorics::list-derangements n
52 ::math::combinatorics::list-powerset n
54 ::math::combinatorics::permutationObj new/create NAME n
56 $perm next
58 $perm reset
60 $perm setElements elements
62 $perm setElements
64 ::math::combinatorics::combinationObj new/create NAME n k
66 $combin next
68 $combin reset
70 $combin setElements elements
72 $combin setElements
74______________________________________________________________________________
76
78 The math package contains implementations of several functions useful
79 in combinatorial problems. The math::combinatorics extends the collec‐
80 tions based on features in Tcl 8.6. Note: the meaning of the parti‐
81 tionP function, Catalan and Stirling numbers is explained on the Math‐
82 World website [http://mathworld.wolfram.com]
83
85 ::math::ln_Gamma z
86 Returns the natural logarithm of the Gamma function for the ar‐
87 gument z.
88 The Gamma function is defined as the improper integral from zero
90 to positive infinity of
91 t**(x-1)*exp(-t) dt
94 The approximation used in the Tcl Math Library is from Lanczos, ISIAM
97 J. Numerical Analysis, series B, volume 1, p. 86. For "x > 1", the ab‐
98 solute error of the result is claimed to be smaller than 5.5*10**-10 --
99 that is, the resulting value of Gamma when
100 exp( ln_Gamma( x) )
103 is computed is expected to be precise to better than nine sig‐
106 nificant figures.
107 ::math::factorial x
109 Returns the factorial of the argument x.
110 For integer x, 0 <= x <= 12, an exact integer result is re‐
112 turned.
113 For integer x, 13 <= x <= 21, an exact floating-point result is
115 returned on machines with IEEE floating point.
116 For integer x, 22 <= x <= 170, the result is exact to 1 ULP.
118 For real x, x >= 0, the result is approximated by computing
120 Gamma(x+1) using the ::math::ln_Gamma function, and the result
121 is expected to be precise to better than nine significant fig‐
122 ures.
123 It is an error to present x <= -1 or x > 170, or a value of x
125 that is not numeric.
126 ::math::choose n k
128 Returns the binomial coefficient C(n, k)
129 C(n,k) = n! / k! (n-k)!
132 If both parameters are integers and the result fits in 32 bits,
135 the result is rounded to an integer.
136 Integer results are exact up to at least n = 34. Floating point
138 results are precise to better than nine significant figures.
139 ::math::Beta z w
141 Returns the Beta function of the parameters z and w.
142 Beta(z,w) = Beta(w,z) = Gamma(z) * Gamma(w) / Gamma(z+w)
145 Results are returned as a floating point number precise to bet‐
148 ter than nine significant digits provided that w and z are both
149 at least 1.
150 ::math::combinatorics::permutations n
152 Return the number of permutations of n items. The returned num‐
153 ber is always an integer, it is not limited by the range of
154 32-or 64-bits integers using the arbitrary precision integers
155 available in Tcl 8.5 and later.
156 int n The number of items to be permuted.
158 ::math::combinatorics::variations n k
160 Return the number of variations k items selected from the total
161 of n items. The order of the items is taken into account.
162 int n The number of items to be selected from.
164 int k The number of items to be selected in each variation.
166 ::math::combinatorics::combinations n k
168 Return the number of combinations of k items selected from the
169 total of n items. The order of the items is not important.
170 int n The number of items to be selected from.
172 int k The number of items to be selected in each combination.
174 ::math::combinatorics::derangements n
176 Return the number of derangements of n items. A derangement is a
177 permutation where each item is displaced from the original posi‐
178 tion.
179 int n The number of items to be rearranged.
181 ::math::combinatorics::catalan n
183 Return the n'th Catalan number. The number n is expected to be 1
184 or larger. These numbers occur in various combinatorial prob‐
185 lems.
186 int n The index of the Catalan number
188 ::math::combinatorics::firstStirling n m
190 Calculate a Stirling number of the first kind (signed version, m
191 cycles in a permutation of n items)
192 int n Number of items
194 int m Number of cycles
196 ::math::combinatorics::secondStirling n m
198 Calculate a Stirling number of the second kind (m non-empty sub‐
199 sets from n items)
200 int n Number of items
202 int m Number of subsets
204 ::math::combinatorics::partitionP n
206 Calculate the number of ways an integer n can be written as the
207 sum of positive integers.
208 int n Number in question
210 ::math::combinatorics::list-permutations n
212 Return the list of permutations of the numbers 0, ..., n-1.
213 int n The number of items to be permuted.
215 ::math::combinatorics::list-variations n k
217 Return the list of variations of k numbers selected from the
218 numbers 0, ..., n-1. The order of the items is taken into ac‐
219 count.
220 int n The number of items to be selected from.
222 int k The number of items to be selected in each variation.
224 ::math::combinatorics::list-combinations n k
226 Return the list of combinations of k numbers selected from the
227 numbers 0, ..., n-1. The order of the items is ignored.
228 int n The number of items to be selected from.
230 int k The number of items to be selected in each combination.
232 ::math::combinatorics::list-derangements n
234 Return the list of derangements of the numbers 0, ..., n-1.
235 int n The number of items to be rearranged.
237 ::math::combinatorics::list-powerset n
239 Return the list of all subsets of the numbers 0, ..., n-1.
240 int n The number of items to be rearranged.
242 ::math::combinatorics::permutationObj new/create NAME n
244 Create a TclOO object for returning permutations one by one. If
245 the last permutation has been reached an empty list is returned.
246 int n The number of items to be rearranged.
248 $perm next
250 Return the next permutation of n objects.
251 $perm reset
253 Reset the object, so that the command next returns the complete
254 list again.
255 $perm setElements elements
257 Register a list of items to be permuted, using the nextElements
258 command.
259 list elements
261 The list of n items that will be permuted.
262 $perm setElements
264 Return the next permulation of the registered items.
265 ::math::combinatorics::combinationObj new/create NAME n k
267 Create a TclOO object for returning combinations one by one. If
268 the last combination has been reached an empty list is returned.
269 int n The number of items to be rearranged.
271 $combin next
273 Return the next combination of n objects.
274 $combin reset
276 Reset the object, so that the command next returns the complete
277 list again.
278 $combin setElements elements
280 Register a list of items to be permuted, using the nextElements
281 command.
282 list elements
284 The list of n items that will be permuted.
285 $combin setElements
287 Return the next combination of the registered items.
288
290 This document, and the package it describes, will undoubtedly contain
291 bugs and other problems. Please report such in the category math of
292 the Tcllib Trackers [http://core.tcl.tk/tcllib/reportlist]. Please
293 also report any ideas for enhancements you may have for either package
294 and/or documentation.
295 When proposing code changes, please provide unified diffs, i.e the out‐
297 put of diff -u.
298 Note further that attachments are strongly preferred over inlined
300 patches. Attachments can be made by going to the Edit form of the
301 ticket immediately after its creation, and then using the left-most
302 button in the secondary navigation bar.
303
305 Mathematics
306tcllib 2.0 math::combinatorics(n)