Algorithm-Combinatorics

 view release on metacpan or  search on metacpan

Changes  view on Meta::CPAN

    * Added the helper module t/Tester.pm to factor out a common test
      code pattern

    * If k is "out of natural range"" the empty set is returned and a
      warning is issued

    * The iterators return an arrayref, and the implementation was
      revised accordingly to be mathematically correct in edge-cases and
      more forgiving

    * I can't stand that DIAGNOSTICS::Errors section, so many croaks on
      boundary conditions are so unperlish! The module has just a couple
      of days so I am on time to fix this

0.02  November 3 2005

    * README revised

    * DEPENDENCIES added to POD

    * DIAGNOSTICS added to POD

Combinatorics.pm  view on Meta::CPAN

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

Combinatorics.pm  view on Meta::CPAN

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

README  view on Meta::CPAN

    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

README  view on Meta::CPAN

        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.