(defun permutations (bag)
  "Return a list of all the permutations of the input."
  ;; If the input is nil, there is only one permutation:
  ;; nil itself
  (if (null bag) 
      '(())
      ;; Otherwise, take an element, e, out of the bag.
      ;; Generate all permutations of the remaining elements,
      ;; And add e to the front of each of these.
      ;; Do this for all possible e to generate all permutations.
      (mapcan #'(lambda (e)
                  (mapcar #'(lambda (p) (cons e p))
                          (permutations
                            (remove e bag :count 1))))
              bag)))
[download]

Lisp's command of lists shines in this example, and replicating the code in Perl as succinctly (without sacrificing readability) is quite challenging. What I paste below is a straightforward implementation, without delving too much into succinctness.

First, lets define a couple of helper functions:

sub is_empty_list
{
    return @{$_[0]} == 0;
}


# remove ($what, $list, $howmany)
#
# Removes $what from the list $list up to $howmany times.
# If $howmany is not provided, removes all occurrences of $what.
#
sub remove
{
    my $what = $_[0];
    my $list = $_[1];
    my $howmany = defined $_[2] ? $_[2] : -1;
    my @ret = ();
    
    foreach my $elem (@{$list})
    {
        push @ret, $elem unless ($elem == $what and $howmany-- > 0);
    }

    return \@ret;
}
[download]

remove would look good if it were not for the argument collection. Named arguments with support for optional arguments that have default values would be of great help. Happily, it will be provided in Perl6, and this function will look much better.

Now, to the permutations function itself:

sub permutations 
{
    my $bag = $_[0];
    
    if (is_empty_list($bag))
    {
        return [[]];
    }
    
    my $perms = [];

    foreach my $elem (@$bag)
    {
        foreach my $perm (@{permutations(remove($elem, $bag, 1))})
        {
            unshift(@{$perm}, $elem);
            push(@{$perms}, $perm);
        }
    }
    
    return $perms;
}
[download]

This could have been made much nicer if Perl had a sane way to write nested maps... Also, it seems to me that unshift and push would be much better understood as prepend and append.

Any ideas/suggestion to make this code more elegant ?