NAME

Algorithm::Combinatorics - Efficient generation of combinatorial sequences

SYNOPSIS

use Algorithm::Combinatorics qw(permutations);

my @data = ("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.02.

DESCRIPTION

Algorithm::Combinatorics is an efficient generator of combinatorial sequences, where efficient means:

• Speed: The core loops are written in C.

• Memory: No recursion and no stacks are used.

Tuples are generated in lexicographic order.

SUBROUTINES

Algorithm::Combinatorics provides these subroutines:

permutations(\@data)
variations(\@data, $k)
variations_with_repetition(\@data, $k)
combinations(\@data, $k)
combinations_with_repetition(\@data, $k)

All of them are context-sensitive:

• In scalar context the subroutines return an iterator that responds to the next method. Using this object you can iterate over the sequence of tuples one by one. Since no recursion and no stacks are used the memory usage is minimal. We can iterate over sequences of virtually any size.

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

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)

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 the

permutations(\@data);

is equivalent to

variations(\@data, scalar @data);

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)

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.

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)

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

Useless use of %s in void context

A subroutine was called in void context.

Errors

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

Parameter data cannot be empty

A subroutine was called with an empty array of data.

Parameter k must be greater than or equal to 1

A subroutine was called with a value for k less than 1.

Strickly speaking k could be 0. There is one variation of {1, 2, 3} with length 0, namely the empty list. But I find this corner case of no practical use and interferes with the usage of iterators. I would expect them to return lists, not (or in addition to) arrayrefs. Since assigning an empty list to an array in scalar context evaluates to false, the mandatory iteration is not possible.

The choice has been to rule k = 0 out.

Parameter k is greater than the length of data

A subroutine that computes something where k has to be less than or equal to the size of data was called with a k that didn't satisfy such constraint.

DEPENDENCIES

Algorithm::Combinatorics uses Test::More for testing, Scalar::Util for reftype(), and Inline::C for XS.

SEE ALSO

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

AUTHOR

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

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.

COPYRIGHT & LICENSE

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