(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)))


##</code><code>##

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

##</code><code>##

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