Here is the beggining of a solution. It gives you all combinations of lenght x for a given set. So you could call it once for each length of your set and combine all those, to get all combinations of all lenghts.

Fun bit of recursion here. No promises it will always work.

use strict;

my @array = ["a","b","c","d"];
my $newlist = combine(2,@array);
foreach my $list (@$newlist)
{
    print "[" . join(",", @$list) . "]\n";
}


# takes a list of items
# returns a list of lists of those items for each combination
sub combine {
    my $length = shift;
    my $items = shift;    
    my @list;
    if ($length == 1)
    {
        foreach my $item (@$items)
        {
            push @list,[$item];
        }
    }
    else
    {
        my $l = length(@$items) + 1;
        foreach (0..$l)                     # once for each item
        {
            my $tempa = shift @$items;      # get first item(a)
            
            # get permutations for this set, but one 
            # shorter (without current item)
            my $templist = combine($length-1,$items);  
            foreach my $i (@$templist)
            {
                unshift @$i,$tempa;        
                push @list,$i;
            }
            push @$items,$tempa;
        }
    }
    return [@list];
}

1;
[download]

Before getting your response, I found Algorithm::ChooseSubset which takes the same tact. I'm working on that approach now...if I get it to work correctly, I'll post the solution. In essence, it does the same thing yours does!