1Combinatorics(3)      User Contributed Perl Documentation     Combinatorics(3)
2
3
4

NAME

6       Algorithm::Combinatorics - Efficient generation of combinatorial
7       sequences
8

SYNOPSIS

10        use Algorithm::Combinatorics qw(permutations);
11
12        my @data = qw(a b c);
13
14        # scalar context gives an iterator
15        my $iter = permutations(\@data);
16        while (my $p = $iter->next) {
17            # ...
18        }
19
20        # list context slurps
21        my @all_permutations = permutations(\@data);
22

VERSION

24       This documentation refers to Algorithm::Combinatorics version 0.26.
25

DESCRIPTION

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
32       Tuples are generated in lexicographic order, except in subsets().
33

SUBROUTINES

35       Algorithm::Combinatorics provides these subroutines:
36
37           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
50       All of them are context-sensitive:
51
52       •   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
56               my $iter = combinations(\@data, $k);
57               while (my $c = $iter->next) {
58                   # ...
59               }
60
61           The next() method returns an arrayref to the next tuple, if any, or
62           "undef" if the sequence is exhausted.
63
64           Memory usage is minimal, no recursion and no stacks are involved.
65
66       •   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
70               my @all_combinations = combinations(\@data, $k);
71
72   permutations(\@data)
73       The permutations of @data are all its reorderings. For example, the
74       permutations of "@data = (1, 2, 3)" are:
75
76           (1, 2, 3)
77           (1, 3, 2)
78           (2, 1, 3)
79           (2, 3, 1)
80           (3, 1, 2)
81           (3, 2, 1)
82
83       The number of permutations of "n" elements is:
84
85           n! = 1,                  if n = 0
86           n! = n*(n-1)*...*1,      if n > 0
87
88       See some values at
89       <http://www.research.att.com/~njas/sequences/A000142>.
90
91   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
98       For example the circular permutations of "@data = (1, 2, 3, 4)" are:
99
100           (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
107       The number of circular permutations of "n" elements is:
108
109               n! = 1,                      if 0 <= n <= 1
110           (n-1)! = (n-1)*(n-2)*...*1,      if n > 1
111
112       See a few numbers in a comment of
113       <http://www.research.att.com/~njas/sequences/A000142>.
114
115   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
121           (2, 3, 1)
122           (3, 1, 2)
123
124       The number of derangements of "n" elements is:
125
126           d(n) = 1,                       if n = 0
127           d(n) = n*d(n-1) + (-1)**n,      if n > 0
128
129       See some values at
130       <http://www.research.att.com/~njas/sequences/A000166>.
131
132   complete_permutations(\@data)
133       This is an alias for "derangements", documented above.
134
135   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
140           (1, 2)
141           (1, 3)
142           (2, 1)
143           (2, 3)
144           (3, 1)
145           (3, 2)
146
147       For this to make sense, $k has to be less than or equal to the length
148       of @data.
149
150       Note that
151
152           permutations(\@data);
153
154       is equivalent to
155
156           variations(\@data, scalar @data);
157
158       The number of variations of "n" elements taken in groups of "k" is:
159
160           v(n, k) = 1,                        if k = 0
161           v(n, k) = n*(n-1)*...*(n-k+1),      if 0 < k <= n
162
163   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
168           (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
178       Note that $k can be greater than the length of @data. For example, for
179       "@data = (1, 2)" and "$k = 3":
180
181           (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
190       The number of variations with repetition of "n" elements taken in
191       groups of "k >= 0" is:
192
193           vr(n, k) = n**k
194
195   tuples(\@data, $k)
196       This is an alias for "variations", documented above.
197
198   tuples_with_repetition(\@data, $k)
199       This is an alias for "variations_with_repetition", documented above.
200
201   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
206           (1, 2, 3)
207           (1, 2, 4)
208           (1, 3, 4)
209           (2, 3, 4)
210
211       For this to make sense, $k has to be less than or equal to the length
212       of @data.
213
214       The number of combinations of "n" elements taken in groups of "0 <= k
215       <= n" is:
216
217           n choose k = n!/(k!*(n-k)!)
218
219   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
224           (1, 1)
225           (1, 2)
226           (1, 3)
227           (2, 2)
228           (2, 3)
229           (3, 3)
230
231       Note that $k can be greater than the length of @data. For example, for
232       "@data = (1, 2, 3)" and "$k = 4":
233
234           (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
250       The number of combinations with repetition of "n" elements taken in
251       groups of "k >= 0" is:
252
253           n+k-1 over k = (n+k-1)!/(k!*(n-1)!)
254
255   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
261           ((1, 2, 3))
262           ((1, 2), (3))
263           ((1, 3), (2))
264           ((1), (2, 3))
265           ((1), (2), (3))
266
267       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
271       The number of partitions of a set of "n" elements are known as Bell
272       numbers, and satisfy the recursion:
273
274           B(0) = 1
275           B(n+1) = (n over 0)B(0) + (n over 1)B(1) + ... + (n over n)B(n)
276
277       See some values at
278       <http://www.research.att.com/~njas/sequences/A000110>.
279
280       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
285       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
292       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
295           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
300   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
305       The number of subsets of a set of "n" elements is
306
307         2**n
308
309       See some values at
310       <http://www.research.att.com/~njas/sequences/A000079>.
311

CORNER CASES

313       Since version 0.05 subroutines are more forgiving for unsual values of
314       $k:
315
316       •   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 list
318           context returns the empty list. (See "DIAGNOSTICS".)
319
320       •   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
327       •   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
333       In addition, since 0.05 empty @datas are supported as well.
334

EXPORT

336       Algorithm::Combinatorics exports nothing by default. Each of the
337       subroutines can be exported on demand, as in
338
339           use Algorithm::Combinatorics qw(combinations);
340
341       and the tag "all" exports them all:
342
343           use Algorithm::Combinatorics qw(:all);
344

DIAGNOSTICS

346   Warnings
347       The following warnings may be issued:
348
349       Useless use of %s in void context
350           A subroutine was called in void context.
351
352       Parameter k is negative
353           A subroutine was called with a negative k.
354
355       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
359   Errors
360       The following errors may be thrown:
361
362       Missing parameter data
363           A subroutine was called with no parameters.
364
365       Missing parameter k
366           A subroutine that requires a second parameter k was called without
367           one.
368
369       Parameter data is not an arrayref
370           The first parameter is not an arrayref (tested with "reftype()"
371           from Scalar::Util.)
372

DEPENDENCIES

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

BUGS

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

SEE ALSO

385       Math::Combinatorics is a pure Perl module that offers similar features.
386
387       List::PowerSet offers a fast pure-Perl generator of power sets that
388       Algorithm::Combinatorics copies and translates to XS.
389

BENCHMARKS

391       There are some benchmarks in the benchmarks directory of the
392       distribution.
393

REFERENCES

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
399       [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
403       [3] Michael Orlov, Efficient Generation of Set Partitions,
404       <http://www.informatik.uni-ulm.de/ni/Lehre/WS03/DMM/Software/partitions.pdf>.
405

AUTHOR

407       Xavier Noria (FXN), <fxn@cpan.org>
408
410       Copyright 2005-2012 Xavier Noria, all rights reserved.
411
412       This program is free software; you can redistribute it and/or modify it
413       under the same terms as Perl itself.
414
415
416
417perl v5.38.0                      2023-07-20                  Combinatorics(3)
Impressum