1Combinatorics(3) User Contributed Perl Documentation Combinatorics(3)
2
6 Algorithm::Combinatorics - Efficient generation of combinatorial
7 sequences
8
10 use Algorithm::Combinatorics qw(permutations);
11 my @data = qw(a b c);
13 # scalar context gives an iterator
15 my $iter = permutations(\@data);
16 while (my $p = $iter->next) {
17 # ...
18 }
19 # list context slurps
21 my @all_permutations = permutations(\@data);
22
24 This documentation refers to Algorithm::Combinatorics version 0.26.
25
27 Algorithm::Combinatorics is an efficient generator of combinatorial
28 sequences. Algorithms are selected from the literature (work in
29 progress, see "REFERENCES"). Iterators do not use recursion, nor
30 stacks, and are written in C.
31 Tuples are generated in lexicographic order, except in "subsets()".
33
35 Algorithm::Combinatorics provides these subroutines:
36 permutations(\@data)
38 circular_permutations(\@data)
39 derangements(\@data)
40 complete_permutations(\@data)
41 variations(\@data, $k)
42 variations_with_repetition(\@data, $k)
43 tuples(\@data, $k)
44 tuples_with_repetition(\@data, $k)
45 combinations(\@data, $k)
46 combinations_with_repetition(\@data, $k)
47 partitions(\@data[, $k])
48 subsets(\@data[, $k])
49 All of them are context-sensitive:
51 • In scalar context subroutines return an iterator that responds to
53 the "next()" method. Using this object you can iterate over the
54 sequence of tuples one by one this way:
55 my $iter = combinations(\@data, $k);
57 while (my $c = $iter->next) {
58 # ...
59 }
60 The "next()" method returns an arrayref to the next tuple, if any,
62 or "undef" if the sequence is exhausted.
63 Memory usage is minimal, no recursion and no stacks are involved.
65 • In list context subroutines slurp the entire set of tuples. This
67 behaviour is offered for convenience, but take into account that
68 the resulting array may be really huge:
69 my @all_combinations = combinations(\@data, $k);
71 permutations(\@data)
73 The permutations of @data are all its reorderings. For example, the
74 permutations of "@data = (1, 2, 3)" are:
75 (1, 2, 3)
77 (1, 3, 2)
78 (2, 1, 3)
79 (2, 3, 1)
80 (3, 1, 2)
81 (3, 2, 1)
82 The number of permutations of "n" elements is:
84 n! = 1, if n = 0
86 n! = n*(n-1)*...*1, if n > 0
87 See some values at
89 <http://www.research.att.com/~njas/sequences/A000142>.
90 circular_permutations(\@data)
92 The circular permutations of @data are its arrangements around a
93 circle, where only relative order of elements matter, rather than their
94 actual position. Think possible arrangements of people around a
95 circular table for dinner according to whom they have to their right
96 and left, no matter the actual chair they sit on.
97 For example the circular permutations of "@data = (1, 2, 3, 4)" are:
99 (1, 2, 3, 4)
101 (1, 2, 4, 3)
102 (1, 3, 2, 4)
103 (1, 3, 4, 2)
104 (1, 4, 2, 3)
105 (1, 4, 3, 2)
106 The number of circular permutations of "n" elements is:
108 n! = 1, if 0 <= n <= 1
110 (n-1)! = (n-1)*(n-2)*...*1, if n > 1
111 See a few numbers in a comment of
113 <http://www.research.att.com/~njas/sequences/A000142>.
114 derangements(\@data)
116 The derangements of @data are those reorderings that have no element in
117 its original place. In jargon those are the permutations of @data with
118 no fixed points. For example, the derangements of "@data = (1, 2, 3)"
119 are:
120 (2, 3, 1)
122 (3, 1, 2)
123 The number of derangements of "n" elements is:
125 d(n) = 1, if n = 0
127 d(n) = n*d(n-1) + (-1)**n, if n > 0
128 See some values at
130 <http://www.research.att.com/~njas/sequences/A000166>.
131 complete_permutations(\@data)
133 This is an alias for "derangements", documented above.
134 variations(\@data, $k)
136 The variations of length $k of @data are all the tuples of length $k
137 consisting of elements of @data. For example, for "@data = (1, 2, 3)"
138 and "$k = 2":
139 (1, 2)
141 (1, 3)
142 (2, 1)
143 (2, 3)
144 (3, 1)
145 (3, 2)
146 For this to make sense, $k has to be less than or equal to the length
148 of @data.
149 Note that
151 permutations(\@data);
153 is equivalent to
155 variations(\@data, scalar @data);
157 The number of variations of "n" elements taken in groups of "k" is:
159 v(n, k) = 1, if k = 0
161 v(n, k) = n*(n-1)*...*(n-k+1), if 0 < k <= n
162 variations_with_repetition(\@data, $k)
164 The variations with repetition of length $k of @data are all the tuples
165 of length $k consisting of elements of @data, including repetitions.
166 For example, for "@data = (1, 2, 3)" and "$k = 2":
167 (1, 1)
169 (1, 2)
170 (1, 3)
171 (2, 1)
172 (2, 2)
173 (2, 3)
174 (3, 1)
175 (3, 2)
176 (3, 3)
177 Note that $k can be greater than the length of @data. For example, for
179 "@data = (1, 2)" and "$k = 3":
180 (1, 1, 1)
182 (1, 1, 2)
183 (1, 2, 1)
184 (1, 2, 2)
185 (2, 1, 1)
186 (2, 1, 2)
187 (2, 2, 1)
188 (2, 2, 2)
189 The number of variations with repetition of "n" elements taken in
191 groups of "k >= 0" is:
192 vr(n, k) = n**k
194 tuples(\@data, $k)
196 This is an alias for "variations", documented above.
197 tuples_with_repetition(\@data, $k)
199 This is an alias for "variations_with_repetition", documented above.
200 combinations(\@data, $k)
202 The combinations of length $k of @data are all the sets of size $k
203 consisting of elements of @data. For example, for "@data = (1, 2, 3,
204 4)" and "$k = 3":
205 (1, 2, 3)
207 (1, 2, 4)
208 (1, 3, 4)
209 (2, 3, 4)
210 For this to make sense, $k has to be less than or equal to the length
212 of @data.
213 The number of combinations of "n" elements taken in groups of "0 <= k
215 <= n" is:
216 n choose k = n!/(k!*(n-k)!)
218 combinations_with_repetition(\@data, $k);
220 The combinations of length $k of an array @data are all the bags of
221 size $k consisting of elements of @data, with repetitions. For example,
222 for "@data = (1, 2, 3)" and "$k = 2":
223 (1, 1)
225 (1, 2)
226 (1, 3)
227 (2, 2)
228 (2, 3)
229 (3, 3)
230 Note that $k can be greater than the length of @data. For example, for
232 "@data = (1, 2, 3)" and "$k = 4":
233 (1, 1, 1, 1)
235 (1, 1, 1, 2)
236 (1, 1, 1, 3)
237 (1, 1, 2, 2)
238 (1, 1, 2, 3)
239 (1, 1, 3, 3)
240 (1, 2, 2, 2)
241 (1, 2, 2, 3)
242 (1, 2, 3, 3)
243 (1, 3, 3, 3)
244 (2, 2, 2, 2)
245 (2, 2, 2, 3)
246 (2, 2, 3, 3)
247 (2, 3, 3, 3)
248 (3, 3, 3, 3)
249 The number of combinations with repetition of "n" elements taken in
251 groups of "k >= 0" is:
252 n+k-1 over k = (n+k-1)!/(k!*(n-1)!)
254 partitions(\@data[, $k])
256 A partition of @data is a division of @data in separate pieces.
257 Technically that's a set of subsets of @data which are non-empty,
258 disjoint, and whose union is @data. For example, the partitions of
259 "@data = (1, 2, 3)" are:
260 ((1, 2, 3))
262 ((1, 2), (3))
263 ((1, 3), (2))
264 ((1), (2, 3))
265 ((1), (2), (3))
266 This subroutine returns in consequence tuples of tuples. The top-level
268 tuple (an arrayref) represents the partition itself, whose elements are
269 tuples (arrayrefs) in turn, each one representing a subset of @data.
270 The number of partitions of a set of "n" elements are known as Bell
272 numbers, and satisfy the recursion:
273 B(0) = 1
275 B(n+1) = (n over 0)B(0) + (n over 1)B(1) + ... + (n over n)B(n)
276 See some values at
278 <http://www.research.att.com/~njas/sequences/A000110>.
279 If you pass the optional parameter $k, the subroutine generates only
281 partitions of size $k. This uses an specific algorithm for partitions
282 of known size, which is more efficient than generating all partitions
283 and filtering them by size.
284 Note that in that case the subsets themselves may have several sizes,
286 it is the number of elements of the partition which is $k. For instance
287 if @data has 5 elements there are partitions of size 2 that consist of
288 a subset of size 2 and its complement of size 3; and partitions of size
289 2 that consist of a subset of size 1 and its complement of size 4. In
290 both cases the partitions have the same size, they have two elements.
291 The number of partitions of size "k" of a set of "n" elements are known
293 as Stirling numbers of the second kind, and satisfy the recursion:
294 S(0, 0) = 1
296 S(n, 0) = 0 if n > 0
297 S(n, 1) = S(n, n) = 1
298 S(n, k) = S(n-1, k-1) + kS(n-1, k)
299 subsets(\@data[, $k])
301 This subroutine iterates over the subsets of data, which is assumed to
302 represent a set. If you pass the optional parameter $k the iteration
303 runs over subsets of data of size $k.
304 The number of subsets of a set of "n" elements is
306 2**n
308 See some values at
310 <http://www.research.att.com/~njas/sequences/A000079>.
311
313 Since version 0.05 subroutines are more forgiving for unsual values of
314 $k:
315 • If $k is less than zero no tuple exists. Thus, the very first call
317 to the iterator's "next()" method returns "undef", and a call in
318 list context returns the empty list. (See "DIAGNOSTICS".)
319 • If $k is zero we have one tuple, the empty tuple. This is a
321 different case than the former: when $k is negative there are no
322 tuples at all, when $k is zero there is one tuple. The rationale
323 for this behaviour is the same rationale for n choose 0 = 1: the
324 empty tuple is a subset of @data with "$k = 0" elements, so it
325 complies with the definition.
326 • If $k is greater than the size of @data, and we are calling a
328 subroutine that does not generate tuples with repetitions, no tuple
329 exists. Thus, the very first call to the iterator's "next()" method
330 returns "undef", and a call in list context returns the empty list.
331 (See "DIAGNOSTICS".)
332 In addition, since 0.05 empty @datas are supported as well.
334
336 Algorithm::Combinatorics exports nothing by default. Each of the
337 subroutines can be exported on demand, as in
338 use Algorithm::Combinatorics qw(combinations);
340 and the tag "all" exports them all:
342 use Algorithm::Combinatorics qw(:all);
344
346 Warnings
347 The following warnings may be issued:
348 Useless use of %s in void context
350 A subroutine was called in void context.
351 Parameter k is negative
353 A subroutine was called with a negative k.
354 Parameter k is greater than the size of data
356 A subroutine that does not generate tuples with repetitions was
357 called with a k greater than the size of data.
358 Errors
360 The following errors may be thrown:
361 Missing parameter data
363 A subroutine was called with no parameters.
364 Missing parameter k
366 A subroutine that requires a second parameter k was called without
367 one.
368 Parameter data is not an arrayref
370 The first parameter is not an arrayref (tested with "reftype()"
371 from Scalar::Util.)
372
374 Algorithm::Combinatorics is known to run under perl 5.6.2. The
375 distribution uses Test::More and FindBin for testing, Scalar::Util for
376 "reftype()", and XSLoader for XS.
377
379 Please report any bugs or feature requests to
380 "bug-algorithm-combinatorics@rt.cpan.org", or through the web interface
381 at
382 <http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Algorithm-Combinatorics>.
383
385 Math::Combinatorics is a pure Perl module that offers similar features.
386 List::PowerSet offers a fast pure-Perl generator of power sets that
388 Algorithm::Combinatorics copies and translates to XS.
389
391 There are some benchmarks in the benchmarks directory of the
392 distribution.
393
395 [1] Donald E. Knuth, The Art of Computer Programming, Volume 4,
396 Fascicle 2: Generating All Tuples and Permutations. Addison Wesley
397 Professional, 2005. ISBN 0201853930.
398 [2] Donald E. Knuth, The Art of Computer Programming, Volume 4,
400 Fascicle 3: Generating All Combinations and Partitions. Addison Wesley
401 Professional, 2005. ISBN 0201853949.
402 [3] Michael Orlov, Efficient Generation of Set Partitions,
404 <http://www.informatik.uni-ulm.de/ni/Lehre/WS03/DMM/Software/partitions.pdf>.
405
407 Xavier Noria (FXN), <fxn@cpan.org>
408
410 Copyright 2005-2012 Xavier Noria, all rights reserved.
411 This program is free software; you can redistribute it and/or modify it
413 under the same terms as Perl itself.
414perl v5.34.0 2021-07-22 Combinatorics(3)