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

## Answers

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

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.