Seems to me that you've fallen into a pattern of looking at things in terms of combinations, permutations & powersets et al.

The basic problem is a simply a lookup problem, but as you point out, hashes don't work for this because of ordering. You could build a trie, but they are not efficient built in terms of perl's available data structures.

The alternative is to use a set of bitstrings to to index the words containing each of the letters. The bitstring for 'a', contains a set bit at the offset corresponding to any word in the dictionary that contains an 'a'. Same for 'b', etc.

To find all the words in the dictionary that contain only those given letters, you first OR all the bitstrings for the given letters together, and then, AND NOT the result with each of the remaining alphabet. You end up with a mask where each set bit corresponds to a complient word in the dictionary.

Not sure how my crude implementation stack up against yours, but it should compare favourably (assuming I understood the rules):

#! perl -slw
use strict;
use Data::Dump qw[ pp ];

sub uniq{ my %x; @x{@_} = (); keys %x }

my @words = do{ local *ARGV = ['words.txt']; <> };
chomp @words;

@words = grep length() > 2, @words;

my %index;

@index{ 'a' .. 'z' } = map chr(0) x int( ( @words + 8 )/8 ), 1 .. 26;

for my $iWords ( 0 .. $#words ) {
    for my $char ( sort uniq split '', $words[ $iWords ] ) {
        vec( $index{ $char }, $iWords, 1 ) = 1;
    }
}

while( chomp( my $given = <STDIN> ) ) {
    my @given = split '', $given;
    my @excludes = grep{ !(1+index $given, $_ ) } 'a'..'z';

    my $mask = chr(0) x int( ( @words + 8 )/8 );

    $mask |= $_ for @index{ @given };
    $mask &= ~ $index{ $_ } for @excludes;

    my $count = unpack "%32b*", $mask;

    print "Found $count words:\n";

    vec( $mask, $_, 1 ) and print $words[ $_ ]
        for 0 .. $#words;

    print "\n\n";
}

__END__
c:\test>790206
fred
Found 30 words:

deed
deeded
deer
def
defer
deferred
deffer
ere
err
erred
fed
fee
feed
feeder
free
freed
freer
red
redder
reed
reef
reefed
reefer
ref
refer
referee
refereed
referred
referrer
reffed
[download]