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

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.

USAGE

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 in each iteration the memory usage is minimal.

• 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 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);

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.