Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
Combinatorics(3)      User Contributed Perl Documentation     Combinatorics(3)

NAME
       Algorithm::Combinatorics	- Efficient generation of combinatorial
       sequences

SYNOPSIS
	use Algorithm::Combinatorics qw(permutations);

	my @data = qw(a	b c);

	# scalar context gives an iterator
	my $iter = permutations(\@data);
	while (my $p = $iter->next) {
	    # ...
	}

	# list context slurps
	my @all_permutations = permutations(\@data);

VERSION
       This documentation refers to Algorithm::Combinatorics version 0.26.

DESCRIPTION
       Algorithm::Combinatorics	is an efficient	generator of combinatorial
       sequences. Algorithms are selected from the literature (work in
       progress, see "REFERENCES"). Iterators do not use recursion, nor
       stacks, and are written in C.

       Tuples are generated in lexicographic order, except in "subsets()".

SUBROUTINES
       Algorithm::Combinatorics	provides these subroutines:

	   permutations(\@data)
	   circular_permutations(\@data)
	   derangements(\@data)
	   complete_permutations(\@data)
	   variations(\@data, $k)
	   variations_with_repetition(\@data, $k)
	   tuples(\@data, $k)
	   tuples_with_repetition(\@data, $k)
	   combinations(\@data,	$k)
	   combinations_with_repetition(\@data,	$k)
	   partitions(\@data[, $k])
	   subsets(\@data[, $k])

       All of them are context-sensitive:

       o   In scalar context subroutines return	an iterator that responds to
	   the "next()"	method.	Using this object you can iterate over the
	   sequence of tuples one by one this way:

	       my $iter	= combinations(\@data, $k);
	       while (my $c = $iter->next) {
		   # ...
	       }

	   The "next()"	method returns an arrayref to the next tuple, if any,
	   or "undef" if the sequence is exhausted.

	   Memory usage	is minimal, no recursion and no	stacks are involved.

       o   In list context subroutines slurp the entire	set of tuples. This
	   behaviour is	offered	for convenience, but take into account that
	   the resulting array may be really huge:

	       my @all_combinations = combinations(\@data, $k);

   permutations(\@data)
       The permutations	of @data are all its reorderings. For example, the
       permutations of "@data =	(1, 2, 3)" are:

	   (1, 2, 3)
	   (1, 3, 2)
	   (2, 1, 3)
	   (2, 3, 1)
	   (3, 1, 2)
	   (3, 2, 1)

       The number of permutations of "n" elements is:

	   n! =	1,		    if n = 0
	   n! =	n*(n-1)*...*1,	    if n > 0

       See some	values at
       <http://www.research.att.com/~njas/sequences/A000142>.

   circular_permutations(\@data)
       The circular permutations of @data are its arrangements around a
       circle, where only relative order of elements matter, rather than their
       actual position.	Think possible arrangements of people around a
       circular	table for dinner according to whom they	have to	their right
       and left, no matter the actual chair they sit on.

       For example the circular	permutations of	"@data = (1, 2,	3, 4)" are:

	   (1, 2, 3, 4)
	   (1, 2, 4, 3)
	   (1, 3, 2, 4)
	   (1, 3, 4, 2)
	   (1, 4, 2, 3)
	   (1, 4, 3, 2)

       The number of circular permutations of "n" elements is:

	       n! = 1,			    if 0 <= n <= 1
	   (n-1)! = (n-1)*(n-2)*...*1,	    if n > 1

       See a few numbers in a comment of
       <http://www.research.att.com/~njas/sequences/A000142>.

   derangements(\@data)
       The derangements	of @data are those reorderings that have no element in
       its original place. In jargon those are the permutations	of @data with
       no fixed	points.	For example, the derangements of "@data	= (1, 2, 3)"
       are:

	   (2, 3, 1)
	   (3, 1, 2)

       The number of derangements of "n" elements is:

	   d(n)	= 1,			   if n	= 0
	   d(n)	= n*d(n-1) + (-1)**n,	   if n	> 0

       See some	values at
       <http://www.research.att.com/~njas/sequences/A000166>.

   complete_permutations(\@data)
       This is an alias	for "derangements", documented above.

   variations(\@data, $k)
       The variations of length	$k of @data are	all the	tuples of length $k
       consisting of elements of @data.	For example, for "@data	= (1, 2, 3)"
       and "$k = 2":

	   (1, 2)
	   (1, 3)
	   (2, 1)
	   (2, 3)
	   (3, 1)
	   (3, 2)

       For this	to make	sense, $k has to be less than or equal to the length
       of @data.

       Note that

	   permutations(\@data);

       is equivalent to

	   variations(\@data, scalar @data);

       The number of variations	of "n" elements	taken in groups	of "k" is:

	   v(n,	k) = 1,			       if k = 0
	   v(n,	k) = n*(n-1)*...*(n-k+1),      if 0 < k	<= n

   variations_with_repetition(\@data, $k)
       The variations with repetition of length	$k of @data are	all the	tuples
       of length $k consisting of elements of @data, including repetitions.
       For example, for	"@data = (1, 2,	3)" and	"$k = 2":

	   (1, 1)
	   (1, 2)
	   (1, 3)
	   (2, 1)
	   (2, 2)
	   (2, 3)
	   (3, 1)
	   (3, 2)
	   (3, 3)

       Note that $k can	be greater than	the length of @data. For example, for
       "@data =	(1, 2)"	and "$k	= 3":

	   (1, 1, 1)
	   (1, 1, 2)
	   (1, 2, 1)
	   (1, 2, 2)
	   (2, 1, 1)
	   (2, 1, 2)
	   (2, 2, 1)
	   (2, 2, 2)

       The number of variations	with repetition	of "n" elements	taken in
       groups of "k >= 0" is:

	   vr(n, k) = n**k

   tuples(\@data, $k)
       This is an alias	for "variations", documented above.

   tuples_with_repetition(\@data, $k)
       This is an alias	for "variations_with_repetition", documented above.

   combinations(\@data,	$k)
       The combinations	of length $k of	@data are all the sets of size $k
       consisting of elements of @data.	For example, for "@data	= (1, 2, 3,
       4)" and "$k = 3":

	   (1, 2, 3)
	   (1, 2, 4)
	   (1, 3, 4)
	   (2, 3, 4)

       For this	to make	sense, $k has to be less than or equal to the length
       of @data.

       The number of combinations of "n" elements taken	in groups of "0	<= k
       <= n" is:

	   n choose k =	n!/(k!*(n-k)!)

   combinations_with_repetition(\@data,	$k);
       The combinations	of length $k of	an array @data are all the bags	of
       size $k consisting of elements of @data,	with repetitions. For example,
       for "@data = (1,	2, 3)" and "$k = 2":

	   (1, 1)
	   (1, 2)
	   (1, 3)
	   (2, 2)
	   (2, 3)
	   (3, 3)

       Note that $k can	be greater than	the length of @data. For example, for
       "@data =	(1, 2, 3)" and "$k = 4":

	   (1, 1, 1, 1)
	   (1, 1, 1, 2)
	   (1, 1, 1, 3)
	   (1, 1, 2, 2)
	   (1, 1, 2, 3)
	   (1, 1, 3, 3)
	   (1, 2, 2, 2)
	   (1, 2, 2, 3)
	   (1, 2, 3, 3)
	   (1, 3, 3, 3)
	   (2, 2, 2, 2)
	   (2, 2, 2, 3)
	   (2, 2, 3, 3)
	   (2, 3, 3, 3)
	   (3, 3, 3, 3)

       The number of combinations with repetition of "n" elements taken	in
       groups of "k >= 0" is:

	   n+k-1 over k	= (n+k-1)!/(k!*(n-1)!)

   partitions(\@data[, $k])
       A partition of @data is a division of @data in separate pieces.
       Technically that's a set	of subsets of @data which are non-empty,
       disjoint, and whose union is @data. For example,	the partitions of
       "@data =	(1, 2, 3)" are:

	   ((1,	2, 3))
	   ((1,	2), (3))
	   ((1,	3), (2))
	   ((1), (2, 3))
	   ((1), (2), (3))

       This subroutine returns in consequence tuples of	tuples.	The top-level
       tuple (an arrayref) represents the partition itself, whose elements are
       tuples (arrayrefs) in turn, each	one representing a subset of @data.

       The number of partitions	of a set of "n"	elements are known as Bell
       numbers,	and satisfy the	recursion:

	   B(0)	= 1
	   B(n+1) = (n over 0)B(0) + (n	over 1)B(1) + ... + (n over n)B(n)

       See some	values at
       <http://www.research.att.com/~njas/sequences/A000110>.

       If you pass the optional	parameter $k, the subroutine generates only
       partitions of size $k. This uses	an specific algorithm for partitions
       of known	size, which is more efficient than generating all partitions
       and filtering them by size.

       Note that in that case the subsets themselves may have several sizes,
       it is the number	of elements of the partition which is $k. For instance
       if @data	has 5 elements there are partitions of size 2 that consist of
       a subset	of size	2 and its complement of	size 3;	and partitions of size
       2 that consist of a subset of size 1 and	its complement of size 4. In
       both cases the partitions have the same size, they have two elements.

       The number of partitions	of size	"k" of a set of	"n" elements are known
       as Stirling numbers of the second kind, and satisfy the recursion:

	   S(0,	0) = 1
	   S(n,	0) = 0 if n > 0
	   S(n,	1) = S(n, n) = 1
	   S(n,	k) = S(n-1, k-1) + kS(n-1, k)

   subsets(\@data[, $k])
       This subroutine iterates	over the subsets of data, which	is assumed to
       represent a set.	If you pass the	optional parameter $k the iteration
       runs over subsets of data of size $k.

       The number of subsets of	a set of "n" elements is

	 2**n

       See some	values at
       <http://www.research.att.com/~njas/sequences/A000079>.

CORNER CASES
       Since version 0.05 subroutines are more forgiving for unsual values of
       $k:

       o   If $k is less than zero no tuple exists. Thus, the very first call
	   to the iterator's "next()" method returns "undef", and a call in
	   list	context	returns	the empty list.	(See "DIAGNOSTICS".)

       o   If $k is zero we have one tuple, the	empty tuple. This is a
	   different case than the former: when	$k is negative there are no
	   tuples at all, when $k is zero there	is one tuple. The rationale
	   for this behaviour is the same rationale for	n choose 0 = 1:	the
	   empty tuple is a subset of @data with "$k = 0" elements, so it
	   complies with the definition.

       o   If $k is greater than the size of @data, and	we are calling a
	   subroutine that does	not generate tuples with repetitions, no tuple
	   exists. Thus, the very first	call to	the iterator's "next()"	method
	   returns "undef", and	a call in list context returns the empty list.
	   (See	"DIAGNOSTICS".)

       In addition, since 0.05 empty @datas are	supported as well.

EXPORT
       Algorithm::Combinatorics	exports	nothing	by default. Each of the
       subroutines can be exported on demand, as in

	   use Algorithm::Combinatorics	qw(combinations);

       and the tag "all" exports them all:

	   use Algorithm::Combinatorics	qw(:all);

DIAGNOSTICS
   Warnings
       The following warnings may be issued:

       Useless use of %s in void context
	   A subroutine	was called in void context.

       Parameter k is negative
	   A subroutine	was called with	a negative k.

       Parameter k is greater than the size of data
	   A subroutine	that does not generate tuples with repetitions was
	   called with a k greater than	the size of data.

   Errors
       The following errors may	be thrown:

       Missing parameter data
	   A subroutine	was called with	no parameters.

       Missing parameter k
	   A subroutine	that requires a	second parameter k was called without
	   one.

       Parameter data is not an	arrayref
	   The first parameter is not an arrayref (tested with "reftype()"
	   from	Scalar::Util.)

DEPENDENCIES
       Algorithm::Combinatorics	is known to run	under perl 5.6.2. The
       distribution uses Test::More and	FindBin	for testing, Scalar::Util for
       "reftype()", and	XSLoader for XS.

BUGS
       Please report any bugs or feature requests to
       "bug-algorithm-combinatorics@rt.cpan.org", or through the web interface
       at
       <http://rt.cpan.org/NoAuth/ReportBug.html?Queue=Algorithm-Combinatorics>.

SEE ALSO
       Math::Combinatorics is a	pure Perl module that offers similar features.

       List::PowerSet offers a fast pure-Perl generator	of power sets that
       Algorithm::Combinatorics	copies and translates to XS.

BENCHMARKS
       There are some benchmarks in the	benchmarks directory of	the
       distribution.

REFERENCES
       [1] Donald E. Knuth, The	Art of Computer	Programming, Volume 4,
       Fascicle	2: Generating All Tuples and Permutations. Addison Wesley
       Professional, 2005. ISBN	0201853930.

       [2] Donald E. Knuth, The	Art of Computer	Programming, Volume 4,
       Fascicle	3: Generating All Combinations and Partitions. Addison Wesley
       Professional, 2005. ISBN	0201853949.

       [3] Michael Orlov, Efficient Generation of Set Partitions,
       <http://www.informatik.uni-ulm.de/ni/Lehre/WS03/DMM/Software/partitions.pdf>.

AUTHOR
       Xavier Noria (FXN), <fxn@cpan.org>

COPYRIGHT & LICENSE
       Copyright 2005-2012 Xavier Noria, all rights reserved.

       This program is free software; you can redistribute it and/or modify it
       under the same terms as Perl itself.

perl v5.32.1			  2012-02-10		      Combinatorics(3)

NAME | SYNOPSIS | VERSION | DESCRIPTION | SUBROUTINES | CORNER CASES | EXPORT | DIAGNOSTICS | DEPENDENCIES | BUGS | SEE ALSO | BENCHMARKS | REFERENCES | AUTHOR | COPYRIGHT & LICENSE

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=Algorithm::Combinatorics&sektion=3&manpath=FreeBSD+13.0-RELEASE+and+Ports>

home | help