How do I permute N elements of a list?

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 should work on any list:

    #!/usr/bin/perl -n
    # tsc-permute: permute each word of input
    permute([split], []);
    sub permute {
        my @items = @{ $_[0] };
        my @perms = @{ $_[1] };
        unless (@items) {
            print "@perms\n";
	} else {
            my(@newitems,@newperms,$i);
            foreach $i (0 .. $#items) {
                @newitems = @items;
                @newperms = @perms;
                unshift(@newperms, splice(@newitems, $i, 1));
                permute([@newitems], [@newperms]);
	    }
	}
    }

Unfortunately, this algorithm is very inefficient. The Algorithm::Permute module from CPAN runs at least an order of magnitude faster. If you don't have a C compiler (or a binary distribution of Algorithm::Permute), then you can use List::Permutor which is written in pure Perl, and is still several times faster than the algorithm above.

Back to perlfaq4