How can I generate all permutations of an array in Perl?

Question

What's the best (elegant, simple, efficient) way to generate all n! permutations of an array in perl?

For example, if I have an array @arr = (0, 1, 2), I want to output all permutations:

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

It should probably be a function that returns an iterator (lazy/delayed evaluation because n! can become so impossibly large), so it can be called like this:

my @arr = (0, 1, 2);
my $iter = getPermIter(@arr);
while (my @perm = $iter->next() ){
    print "@perm\n";
}

Answer 1

You could use Algorithm::Permute and maybe Iterating Over Permutations (The Perl Journal, Fall 1998) is an interesting read for you.

Answer 2

I suggest you use List::Permutor:

use List::Permutor;

my $permutor = List::Permutor->new( 0, 1, 2);
while ( my @permutation = $permutor->next() ) {
    print "@permutation\n";
}

Answer 3

Take a look at Iterator::Array::Jagged.

Answer 4

If you want to write your own, a recursive algorithm s.t. it would pick one item out of the array, and make the call to itself with the smaller array, until the array's of size one.

It should be quite clean.

Answer 5

I recommend looking at an algorithm for generating permutations in lexicographical order, which is how I recently solved Problem 24. When the number of items in the array grows large, it becomes expensive to store and sort permutations later on.

It looks like List::Permutor, which was suggested by Manni, generates numerically sorted permutations. That's what I'd go with using Perl. Let us know how it turns out.

Answer 6

Perlmonks has some examples: http://www.perlmonks.org/?node_id=503904

Answer 7

See perlfaq4: "How do I permute N elements of a list?"