Short survey of modules for combinations and permutations

This is a short look at some modules for generating combinations and permutations. There are likely more modules that aren't listed. RosettaCode has examples of writing the combinations and permutations functions by hand.

Combinations and Permutations
Module Impl Comb Perm Comb w/rep Perm w/rep Derange Speed Order Comments
Algorithm::Combinatorics XS yes yes yes yes yes + Lexico Fast iterator or array
ntheory XS yes yes no no no ++ Lexico Fast block call
Math::Combinatorics Perl yes yes no no yes - - Impl Iterator or array
Algorithm::FastPermute XS no yes no no no +++ Impl Fast block call
Algorithm::Permute XS no yes no no no + Impl Iterator or fast block call
Algorithm::Loops Perl no yes no no no + Impl Iterator
List::Permutor Perl no yes no no no - Lexico Iterator
Iterator::Misc Perl no yes no no no - - Lexico Iterator
Math::Permute::Array Perl no yes no no no - - Impl Iterator or index
Math::Permute::List Perl no yes no no no Impl Block call
Math::GSL::Permutation XS no yes no no no - Lexico function interface
Math::Disarrange::List Perl no no no no yes Impl Block call
Math::GSL::Combination XS yes no no no no + Lexico iterator or by index

For counting the total number rather than generating actual vectors, Math::Counting, ntheory, or Math::Pari probably have what you need. Also see the RosettaCode task.

Some modules such as Algorithm::Combinatorics, ntheory, and List::Permutor give results in guaranteed lexicographic order. The other modules return data in an order corresponding to whatever internal algorithm is used. For an example unsorted 7 element array, each of the "Impl"-order modules gave a unique sequence (that is, each modules gave a different sequence from any other), while all "Lexico"-order modules gave identical sequences.

The speed is an approximate rating of how fast the permutations or combinations are generated with a relatively large set. Looping over the 479 million permutations of a 12 item set takes only 12 seconds for Algorithm::FastPermute, 1 minute for ntheory, 6 minutes for Algorithm::Permute, 12 minutes for Algorithm::Combinatorics and Algorithm::Loops, 30 minutes for List::Permutor, 37 minutes for Math::Combinatorics, 39 minutes for Math::GSL::Permutation, 42 minutes for the common example tsc-permute, 48 minutes for Iterator::Misc.

The perlfaq recommends List::Permutor, Algorithm::Permute, and Algorithm::Loops. I believe Algorithm::Combinatorics to be a better choice to point people to, as it is likely to cover all needs and calling styles, not just permutations. The results come in lexicographic order rather than implementation defined. It also has excellent documentation.

In all examples, assume we have done something like this setup, and wish to see all permutations of the data, or all combinations of 3 elements.

        use feature 'say';
        my @data = (qw/apple bread curry donut ├ęclair/);

Algorithm::Combinatorics. This is probably what you're looking for. It has nearly everything you need and is pretty fast. Recommended. If you need the highest speed, Algorithm::FastPermute and ntheory are faster.

        use Algorithm::Combinatorics qw/combinations permutations/;

        my $citer = combinations(\@data, 3);
        while (my $c = $citer->next) { say "@$c"; }

        my $piter = permutations(\@data);
        while (my $p = $piter->next) { say "@$p"; }

ntheory. XS and Perl block calls for permutations and combinations. Note that the source array isn't directly used -- each block invocation is given an array of indices rather than a direct permutation/combination of the source array.

        use ntheory qw/forcomb forperm/;

        forcomb { say "@data[@_]" } scalar(@data),3;

        forperm { say "@data[@_]" } scalar(@data);

Math::Combinatorics. One of the slowest of the modules tested, but it does combinations, permutations, and derangements all without XS.

        use Math::Combinatorics;
        my $comb = Math::Combinatorics->new(count => 3, data => [@data]);

        while (my @c = $comb->next_combination) { say "@c" }

        while (my @p = $comb->next_permutation) { say "@p" }

Algorithm::FastPermute. The fastest permutation generator -- for large arrays it is about 10x faster than ntheory, 50x faster than Algorithm::Permute, 60-500x faster than the other modules. Modifies the source array, but after a full permutation it will be in the original order.

        use Algorithm::FastPermute qw/permute/;
        permute { say "@data" } @data;

Algorithm::Permute. Decent permutation iterator. Also includes the FastPermute block generator that works just like that example.

        use Algorithm::Permute;
        my $perm = Algorithm::Permute->new(\@data);
        while (my @set = $perm->next) { say "@set" }

Algorithm::Loops. Permutations through an iterator that modifies the source array. Combinations possible with some code. The array must be sorted to work correctly, and if using sorted numbers, you must use NextPermuteNum.

        use Algorithm::Loops qw/NextPermute/;
        do { say "@data" } while NextPermute(@data);

List::Permutor. Yet another permutation iterator.

        use List::Permutor;
        my $perm = List::Permutor->new(@data);
        while (my @set = $perm->next) { say "@set" }

Iterator::Misc. Yet another permutation iterator, also includes various other iteration functions.

        use Iterator::Misc;
        my $iter = ipermute(@data);
        while (!$iter->is_exhausted) { say "@{$iter->value}" }

Math::Permute::Array. Yet another permutation iterator. Has a rather different syntax than most other modules. Also has a block call. Also allows direct access to permutation index, though without defined order.

        use Math::Permute::Array;
        my $perm = Math::Permute::Array->new(\@data);
        say "@{$perm->cur()}";
        for (1 .. $perm->cardinal()-1) { say "@{$perm->next()}" }

Math::Permute::List. A block permutation generator. Permission issue recently fixed, so it installs correctly now.

        use Math::Permute::List;
        permute { say "@_" } @data;

Math::GSL::Permutation. Uses the GSL permutation API, which is function based, with a few (incomplete) helper methods. Not recommended for this task unless you're already using GSL. Uses a different API than Combination. Permutes reasonably fast, but no quick way to retrieve the array of permutations (calling as_list takes 95% of the time). Also note we have to use private class data.

        use Math::GSL::Permutation qw/:all/;
        my $p = Math::GSL::Permutation->new(scalar(@data));
        do {
          say "@data[$p->as_list]";
        } while !gsl_permutation_next($p->{_permutation});

Math::Disarrange::List. A block derangement generator. Permission issue recently fixed, so it installs correctly now.

        use Math::Disarrange::List;
        disarrange { say "@_" } @data;

Math::GSL::Combination. Documentation a bit incomplete. Not recommended for this task unless you're already using GSL. Inconsistent API with Permutation.

        use Math::GSL::Combination qw/:all/;
        my $c = Math::GSL::Combination->new(scalar(@data),3);
        do {
          say "@data[$c->as_list]";
        } while !$c->status();

1 Comment

Leave a comment

About Dana Jacobsen

user-pic I've been using Perl since 1991 (4.010 or so). At some point I realized that while I have used many languages, I enjoy using Perl more than any others.