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

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";
}
```

Use the List::Permutor module on CPAN. If the list is actually an array, try the Algorithm::Permute module (also on CPAN). It's written in XS code and is very efficient:

```use Algorithm::Permute;

my @array = 'a'..'d';
my \$p_iterator = Algorithm::Permute->new ( \@array );

while (my @perm = \$p_iterator->next) {
print "next permutation: (@perm)\n";
}
```

For even faster execution, you could do:

```use Algorithm::Permute;

my @array = 'a'..'d';

Algorithm::Permute::permute {
print "next permutation: (@array)\n";
} @array;
```

Here's a little program that generates all permutations of all the words on each line of input. The algorithm embodied in the permute() function is discussed in Volume 4 (still unpublished) of Knuth's The Art of Computer Programming and will work on any list:

```#!/usr/bin/perl -n
# Fischer-Krause ordered permutation generator

sub permute (&@) {
my \$code = shift;
my @idx = 0..\$#_;
while ( \$code->(@_[@idx]) ) {
my \$p = \$#idx;
--\$p while \$idx[\$p-1] > \$idx[\$p];
my \$q = \$p or return;
push @idx, reverse splice @idx, \$p;
++\$q while \$idx[\$p-1] > \$idx[\$q];
@idx[\$p-1,\$q]=@idx[\$q,\$p-1];
}
}

permute { print "@_\n" } split;
```

The Algorithm::Loops module also provides the NextPermute and NextPermuteNum functions which efficiently find all unique permutations of an array, even if it contains duplicate values, modifying it in-place: if its elements are in reverse-sorted order then the array is reversed, making it sorted, and it returns false; otherwise the next permutation is returned.

NextPermute uses string order and NextPermuteNum numeric order, so you can enumerate all the permutations of 0..9 like this:

```use Algorithm::Loops qw(NextPermuteNum);

my @list= 0..9;
do { print "@list\n" } while NextPermuteNum @list;
```

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";
}
```

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

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.

Try this,

```use strict;
use warnings;

print "Enter the length of the string - ";
my \$n = <> + 0;

my %hash = map { \$_ => 1 } glob "{0,1,2}" x \$n;

foreach my \$key ( keys %hash ) {
print "\$key\n";
}
```

Output: This will give the all possible combinations of the numbers. You can add the logic to filter out the unwanted combinations.

```\$ perl permute_perl.pl
Enter the length of the string - 3
101
221
211
100
001
202
022
021
122
201
002
212
011
121
010
102
210
012
020
111
120
222
112
220
000
200
110
```

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