view release on metacpan or  search on metacpan

README  view on Meta::CPAN

        (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':

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

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

    *   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 `@data's 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.p
    df.

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.