Dana Jacobsen

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.

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]";
          $c->next()
        } while !$c->status();