view release on metacpan or  search on metacpan

Combinatorics.pm  view on Meta::CPAN

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


=head2 combinations_with_repetition(\@data, $k);

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

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

Note that C<$k> can be greater than the length of C<@data>. For example, for C<@data = (1, 2, 3)> and C<$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 C<n> elements taken in groups of C<< k >= 0 >> is:

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


=head2 partitions(\@data[, $k])

A partition of C<@data> is a division of C<@data> in separate pieces. Technically that's a set of subsets of C<@data> which are non-empty, disjoint, and whose union is C<@data>. For example, the partitions of C<@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 C<@data>.

The number of partitions of a set of C<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 L<http://www.research.att.com/~njas/sequences/A000110>.

If you pass the optional parameter C<$k>, the subroutine generates only partitions of size C<$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 I<of the partition> which is C<$k>. For instance if C<@data> has 5 elements there are partitions of size 2 that consist of a subset of size 2 and its c...

The number of partitions of size C<k> of a set of C<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)


=head2 subsets(\@data[, $k])

This subroutine iterates over the subsets of data, which is assumed to represent a set. If you pass the optional parameter C<$k> the iteration runs over subsets of data of size C<$k>.

The number of subsets of a set of C<n> elements is

  2**n

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


=head1 CORNER CASES

Since version 0.05 subroutines are more forgiving for unsual values of C<$k>:

=over 4

=item *

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

=item *

If C<$k> is zero we have one tuple, the empty tuple. This is a different
case than the former: when C<$k> is negative there are no tuples at all,
when C<$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
C<@data> with C<$k = 0> elements, so it complies with the definition.

=item *

If C<$k> is greater than the size of C<@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 C<next()> method
returns C<undef>, and a call in list context returns the empty
list. (See L</DIAGNOSTICS>.)

=back

In addition, since 0.05 empty C<@data>s are supported as well.


=head1 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 C<all> exports them all:

    use Algorithm::Combinatorics qw(:all);


=head1 DIAGNOSTICS

=head2 Warnings

The following warnings may be issued:

=over

=item Useless use of %s in void context

A subroutine was called in void context.

=item Parameter k is negative

A subroutine was called with a negative k.

=item 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.

=back

=head2 Errors

The following errors may be thrown:

=over

=item Missing parameter data

A subroutine was called with no parameters.

=item Missing parameter k

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

=item Parameter data is not an arrayref

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

=back

=head1 DEPENDENCIES

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

=head1 BUGS

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

=head1 SEE ALSO

L<Math::Combinatorics> is a pure Perl module that offers similar features.

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

=head1 BENCHMARKS

There are some benchmarks in the F<benchmarks> directory of the distribution.

=head1 REFERENCES

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

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

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

=head1 AUTHOR

Xavier Noria (FXN), E<lt>fxn@cpan.orgE<gt>

=head1 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.

=cut